[ZJOI2008]骑士

Time Limit: 10 Sec Memory Limit: 162 MB
http://www.lydsy.com/JudgeOnline/problem.php?id=1040http://codevs.cn/problem/1423/

Description

　　Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各
界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境
中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一
个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一
些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出
征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有
的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的
情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战
斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

Input

　　第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力
和他最痛恨的骑士。

Output

　　应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

Sample Input

3
10 2
20 3
30 1

Sample Output

HINT

N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

首先有向边改成无向边，因为a痛恨b，就算b不痛恨a，a、b也不能一起选出

其次n个点n条边，一定有一个环，而且是有且只有一个环

据说这个叫环套树，没有标准定义，大概就是一个环，然后环中有节点还连接着树

通俗点儿就是一个连通块，连通块内有且只有一个环

这里是环套树森林，因为不能保证图连通

碰到环一般都断环为链

dfs每一个连通块，找到环，随便找一条边断掉，然后树形DP

怎么DP？

记录下断掉的边的左右端点x，y

做两遍树形DP，第一次不选x，第二次不选y

取大的累加即可

一个错误：

dfs函数中找到一条要断掉的边后，加了reutrn

想加return是因为随便找一条边断掉，既然找到了返回就行，错，原因有2
1、递归，就算reutrn也不能一次回到主函数
2、（主要原因）dfs除了找断掉的边，还有v数组，标记连通块内节点是否被遍历过,目的是使同一连通块内只DP1轮
如果加了return，看图说话

#include<algorithm>
#include<cstdio>
#define N 1000010
using namespace std;
int tot,to[N*2],next[N*2],front[N],b[N*2];
//b数组：标记边的编号，因为加了2条有向边相当于一条无向边，dp过程中防止走断掉的边 
int v[N],root,tmp,node,n;
bool ok;
long long f[N][2],w[N];
long long ans,k;
void add(int u,int v,int t)
{
    to[++tot]=v;next[tot]=front[u];front[u]=tot;b[tot]=t;
    to[++tot]=u;next[tot]=front[v];front[v]=tot;b[tot]=t;
}
void dfs(int x,int fa)
{
    v[x]=1;
    for(int i=front[x];i;i=next[i])
    {
        int t=to[i];
        if(t==fa) continue;
        if(v[t])
        {
            root=t;
            node=x;
            tmp=b[i];
            //这里不能加return； 
        }
        else dfs(t,x);
    }
}
void dp(int x,int fa)
{
    f[x][0]=0;f[x][1]=w[x];
    for(int i=front[x];i;i=next[i])
    {
        int t=to[i];
        if(b[i]==tmp||t==fa) continue;
        dp(t,x);
        f[x][0]+=max(f[t][0],f[t][1]);
        f[x][1]+=f[t][0];
    }
}
int main()
{
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%d",&w[i],&x);
        add(i,x,i);
    }
    for(int i=1;i<=n;i++)
    {
        if(!v[i])
        {
            dfs(i,0);
            dp(root,0);
            k=f[root][0];
            dp(node,0);
            k=max(k,f[node][0]);
            ans+=k;
        }
    }
    printf("%lld",ans);
}

粘一个每个连通块只DP一次的代码

时间消耗是上面的一半

然而看不懂。。。

#include<cstdio>
#include<queue>
#define N 1000001
using namespace std;
queue<int>q;
int n,w[N],son[N],in[N],v[N],root[N],cnt,bak[N];
long long f[N][4],ans;
void dfs(int x)
{
    v[x]=x;int i;
    for(i=son[x];!v[i];i=son[i]) v[i]=x;
    if(v[i]==x)
    {
        root[++cnt]=i;bak[son[i]]=1;
        --in[son[i]];son[i]=0;
    }
}
void treedp()
{
    int x,y;
    for(int i=1;i<=n;i++)
    {
        f[i][1]=w[i];
        if(!bak[i]) f[i][3]=w[i];
    }
    for(int i=1;i<=n;i++)
     if(!in[i]) q.push(i);
    while(!q.empty())
    {
        x=q.front();q.pop();
        y=son[x];
        if(!y) continue;
        f[y][0]+=max(f[x][1],f[x][0]);
        f[y][1]+=f[x][0];
        f[y][2]+=max(f[x][2],f[x][3]);
        if(!bak[y]) f[y][3]+=f[x][2];
        --in[y];
        if(!in[y]) q.push(y);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&son[i]);
        in[son[i]]++;
    }
    for(int i=1;i<=n;i++) if(!v[i]) dfs(i);
    treedp();
    for(int i=1;i<=cnt;i++) 
        ans+=max(f[root[i]][0],f[root[i]][3]);
    printf("%lld
",ans);
}

View Code