Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
第一行包含一个正整数N，描述骑士团的人数。接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。
对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。
与 BZOJ 1023 仙人掌图 很相似，这题同样也是树形dp+环形dp。
如果是一颗树的话，这题就是典型的水题了。f[i][0]表示以i点为根的树且i点不选的最大获益，f[i][1]表示以i点为根的树且i点被选择的最大获益。转移自己脑补一下吧。
如果存在环的话，我们就可以先将树边dp完，再将环单独抠出来dp。
环上dp有特殊处理技巧——断环为链。
我们假定有个环a1,a2,a3...an。将a1与an的边断开，先假定a1选，a1那么不选的代价就是-inf，dp到an，最后的答案就是f[an][0]，将答案合并到f[a1]中。再假定a1不选，那么a1选的代价就是-inf，dp到an，最后答案就是min(f[an][0],f[an][1])，合并到f[a1]中。(必须卡死一个状态，不然会多许多非法的转移，也就是我们要dp两次。)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 using namespace std; 6 7 #define inf (1ll<<60) 8 #define maxn 1000010 9 int n,cnt = 1,cir[maxn],w[maxn],fa[maxn],side[maxn]; 10 int dfn[maxn],low[maxn],toit[maxn*2],next[maxn*2]; 11 long long f[maxn][2],g[maxn][2],ans; 12 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 17 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 18 return x*f; 19 } 20 21 inline void add(int a,int b) { next[++cnt] = side[a]; toit[cnt] = b; side[a] = cnt; } 22 23 inline void ins(int a,int b) { add(a,b); add(b,a); } 24 25 inline void dp(int root,int last) 26 { 27 int nn = 0; 28 while (last != root) cir[++nn] = last,last = fa[last]; 29 cir[++nn] = root; 30 for (int i = 1;i <= nn;++i) g[cir[i]][0] = f[cir[i]][0],g[cir[i]][1] = f[cir[i]][1]; 31 g[root][1] = inf; 32 for (int i = nn-1;i;--i) 33 { 34 g[cir[i]][0] += min(g[cir[i+1]][0],g[cir[i+1]][1]); 35 g[cir[i]][1] += g[cir[i+1]][0]; 36 } 37 f[root][0] = min(g[cir[1]][0],g[cir[1]][1]); 38 for (int i = 1;i <= nn;++i) g[cir[i]][0] = f[cir[i]][0],g[cir[i]][1] = f[cir[i]][1]; 39 g[root][0] = inf; 40 for (int i = nn-1;i;--i) 41 { 42 g[cir[i]][0] += min(g[cir[i+1]][0],g[cir[i+1]][1]); 43 g[cir[i]][1] += g[cir[i+1]][0]; 44 } 45 f[root][1] = g[cir[1]][0]; 46 } 47 48 inline void dfs(int now) 49 { 50 dfn[now] = low[now] = ++cnt; 51 f[now][0] = w[now]; 52 for (int i = side[now];i;i = next[i]) 53 if (toit[i] != fa[now]) 54 { 55 if (fa[toit[i]] == now) continue; 56 if (!dfn[toit[i]]) fa[toit[i]] = now,dfs(toit[i]); 57 low[now] = min(low[now],low[toit[i]]); 58 if (low[toit[i]] > dfn[now]) 59 { 60 f[now][0] += min(f[toit[i]][0],f[toit[i]][1]); 61 f[now][1] += f[toit[i]][0]; 62 } 63 } 64 for (int i = side[now];i;i = next[i]) 65 if (toit[i] != fa[now] && dfn[toit[i]] > dfn[now] && fa[toit[i]] != now) 66 dp(now,toit[i]); 67 } 68 69 int main() 70 { 71 freopen("1040.in","r",stdin); 72 freopen("1040.out","w",stdout); 73 scanf("%d",&n); 74 for (int i = 1;i <= n;++i) w[i] = read(),ins(read(),i),ans += (long long)w[i]; 75 for (int i = 1;i <= n;++i) 76 if (!dfn[i]) cnt = 0,dfs(i),ans -= min(f[i][0],f[i][1]); 77 printf("%lld",ans); 78 fclose(stdin); fclose(stdout); 79 return 0; 80 }
原文：http://www.cnblogs.com/mmlz/p/4276332.html
