A simple Blog for wyx I've been down the bottle hoping.
BZOJ 1040 骑士 树形$dp$ 基环树
发表于: | 分类: Oi | 评论:0 | 阅读:115

BZOJ 1040 骑士 树形dp 基环树

这题还是挺好写的
↑↑↑↑别听他瞎说,他调了三个小时

首先我们需要建图

但是注意,他虽然说的非常像有向图,但是实际上应该是一个无向图,原因就是一个人不喜欢另一个,那他俩绝对不可能在一起,然后可以在图上进行讨论。

$n$个点$n$个边一定会有环
但是他又没保证是一个连通图,所以也有可能是基环森林 [请记住这一点]
然后的问题就比较好解决了,对于任意一个联通块我们只需要深搜一遍,找到一个环,然后删掉一条边,然后强行然一个端点选或者不选,做树形dp就行了

树形dp就是经典的那个模型
$$f[i] = \sum{g[son[i]]},g[i]=\sum{max(f[son[i]],g[son[i]])}$$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 2000000+5;
const int M = N << 1;
typedef long long LL;
using namespace std;

int head[N];
LL f[N],g[N];
bool vis[N],v[N];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

LL ban,w[N];
int in[N];
int re,n,m,root;

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

void find(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].next)
        if(!in[edge[i].to])
        {
            in[edge[i].to] = 1;
            find(edge[i].to,x);
        }
        else if(edge[i].to!=fa)
            re = x,ban=i,root = edge[i].to,ban = i;
}

void DFS1(int x)
{
    g[x] = 0,f[x] = w[x];
    for(int i=head[x];i;i=edge[i].next)
        if( i!=ban && (i^1)!=ban && !vis[edge[i].to])
        {
            vis[edge[i].to] = 1;
            DFS1(edge[i].to);
            f[x] += g[edge[i].to];
            g[x] += max(g[edge[i].to],f[edge[i].to]);
        }
}

void DFS2(int x)
{
    g[x] = 0,f[x] = w[x];
    for(int i=head[x];i;i=edge[i].next)
        if(i!=ban && (i^1)!=ban && !v[edge[i].to])
        {
            v[edge[i].to] = 1;
            DFS2(edge[i].to);
            f[x] += g[edge[i].to];
            if(edge[i].to == re)
                g[x] += g[edge[i].to];
            else g[x] += max(g[edge[i].to],f[edge[i].to]);  
        } 
}

int main()
{
    n = read();
    for(int i=1;i<=n;++i)
    {
        w[i] = read();
        int tmp = read();
        add(i,tmp);
    }
    LL ans = 0;
    for(int i=1;i<=n;++i)
        if(!in[i])
        {
            LL tmp = 0;
            in[i] = 1,root = -1;
            find(i,-1);
            vis[root] = 1;
            DFS1(root);
            tmp = g[root];
            v[root] = 1;
            DFS2(root);
            tmp = max(tmp,max(f[root],g[root]));
            ans += tmp;
        //  cout<<root<<" " <<tmp<<endl;
        }
    cout<<ans<<endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP