Zoj 3527 Shinryaku! Kero Musume （DP_章鱼图上的树形DP)
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3527
题目大意：一有向图图n个点，n条边，每个点有且只有一条出边。取某个点会有信仰值，同时某个点与它的后继结点同时取的话， 它的信仰值会改变一个值，问怎么取点，使得总信仰值最大
解题思路：拓扑排序+树形DP.这一题的图很有特色，我第一次碰到，官方题解说着实章鱼图，因为每个点只有一条出边，那么要么肯定存在一个或多个环，其他的点依靠着这些环。这题攒了一天才AC，原因是一个int64写成了int，悲催啊...
对于本题，我的解法是先处理章鱼的触须，也就是那些依靠环的边，然后再处理一个个的环。前者就是普通的树形dp，因为每个点只有建或不建两种状态，设dp[i][0]表示i点不建尼姑院获得的最大信仰值，dp[i][1]表示i点建尼姑院获得的最大信仰值，那么触须部分就可以用dp[next][0] = max(dp[i][0],dp[i][1]),dp[next][1] = max(dp[i][0],dp[i][1]-g[i]),或者要加个g[i]是因为同时建尼姑院要减去一定的信仰值。而这个转移的顺序是怎么实现的？我总不能每次都去找叶子然后再一次次往上更新吧？用拓扑排序一步一步往上更新，直到那些环为止，他们的入边永远不为0.
处理完了触须，我们要开始解剖章鱼真身了。因为是个环，我们不能简单地像前面那样转移，那样的话从i点开始到i点结束的时候i点的状态会很混乱。做这题我想到一种解决环上问题的技巧--拆环。随便从某个点开始就将环拆成链。这题分两种情况进入环，当再碰到这个点时特判下，其他情况转移方程同上。
测试数据：
2
3 -1 2
2 -2 1
4
3 -2 2
4 -3 3
2 -1 1
5 -2 2
4
3 0 2
4 0 3
2 0 1
5 0 2
4
3 -2 2
4 -3 3
2 -2 1
5 -9 2
OutPut:
3
9
14
8
C艹代码：
#include <stdio.h>#include <string.h>#include <vector>using namespace std;#define MAX 110000#define int64 long long#define max(a,b) ((a)>(b)?(a):(b))struct node { int val,g,v;}arr[MAX];int st[MAX],top,cnt[MAX],tot; //拓朴排序用int mmap[MAX],n,flag[MAX]; //flag表示是否为环中的点,dp[i][0]表示不在i建，1表示在i建int64 dp[MAX][2],power[MAX][2],ans;void Initial() { ans = top = 0; memset(dp,0,sizeof(dp)); memset(cnt,0,sizeof(cnt));memset(flag,0,sizeof(flag)); memset(power,0,sizeof(power));}void Debug_Input(){ //printf("top = %d\n",tot); for (int i = 1; i <= n; ++i) printf("power[%d][0]=%d power[%d][1]=%d\n",i,power[i][0],i,power[i][1]);}void ToooPooo() { int i,j,k,cur,next; for (i = 1; i <= n; ++i) if (!cnt[i]) st[++top] = i; while (top) { cur = st[top--]; tot++; flag[cur] = 1;//非环中的点 dp[cur][1] += arr[cur].val;//此处建庙则不管后序的情况加上增加的信仰值 next = mmap[cur]; dp[next][0] += max(dp[cur][0],dp[cur][1]); dp[next][1] += max(dp[cur][0],dp[cur][1]+arr[cur].g); cnt[next]--; if (cnt[next] == 0) st[++top] = next; }}void Dfs(int s,int kind) { flag[s] = 1; int next = mmap[s]; power[s][1] += arr[s].val; //此处建庙则不管后序的情况加上增加的信仰值 if (!flag[next]) { power[next][0] = dp[next][0]; power[next][1] = dp[next][1]; power[next][0] += max(power[s][0],power[s][1]); power[next][1] += max(power[s][0],power[s][1]+arr[s].g); Dfs(next,kind); } else { if (kind == 0) power[next][0] = max(power[s][0],power[s][1]); else power[next][1] = max(power[s][0],power[s][1]+arr[s].g); } if (kind == 0) flag[s] = 0;}int main(){ int i,j,k; while (scanf("%d",&n) != EOF) { Initial(); for (i = 1; i <= n; ++i) { scanf("%d%d%d",&arr[i].val,&arr[i].g,&arr[i].v); cnt[arr[i].v]++; mmap[i] = arr[i].v; } ToooPooo(); for (i = 1; i <= n; ++i) if (flag[i] == 0) { int next = mmap[i]; dp[i][1] += arr[i].val; int64 temp = max(dp[i][1],dp[i][0]); power[i][0] = dp[i][0]; power[i][1] = dp[i][1]; power[next][0] = dp[next][0]; power[next][1] = dp[next][1]; power[next][0] += dp[i][0]; power[next][1] += dp[i][0]; flag[i] = 1; Dfs(next,0); temp = max(temp,power[i][0]); power[next][0] = dp[next][0]; power[next][1] = dp[next][1]; power[next][0] += dp[i][1]; power[next][1] += dp[i][1] + arr[i].g; flag[i] = 1; Dfs(next,1); ans += max(temp,power[i][1]);} printf("%lld\n",ans); }}