題目大意：一有向圖圖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艹代碼：
[cpp]
#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);
}
}
