Description
X先生来到了一个奇怪的国家旅行。这个国家有N个城市，每个城市均有且仅有一个机场，但是这机场所有航班只飞往一个城市。每个城市有一个游览价值，第i个城市的游览价值为A[i]。 现在他想知道，从第i个城市出发，并只坐飞机飞往下一个城市，游览价值之和最多是多少（一个城市游览多次只计算1次游览价值）
Input
输入文件travel.in的第1行为一个正整数N。 第2行有N个非负整数A[i]，表示了每个城市的游览价值。 第3行有N个正整数F[i]，表示第i个城市的航班飞往的城市为F[i]，可能出现F[i] = i的情况。
Output
输出文件travel.out包括N行，第i行包含一个非负整数，表示从第i个城市出发游览价值之和的最大值为多少。
题解 解题思路： 每个点出度为1 每个分量就一个环 拓扑排序，没入队过的就是在环上的点 环上的点答案相同，计算出环上点的答案 拓扑排序逆序递推
代码
var a,ans,q,w,ru,order:array[0..200001] of longint; f:array[0..200001] of boolean; n,he,ta,sum,top:longint; procedure init; var i:longint; begin readln(n); for i:=1 to n do read(a[i]); fillchar(ru,sizeof(ru),0); for i:=1 to n do begin read(w[i]); inc(ru[w[i]]); end; fillchar(f,sizeof(f),false); for i:=1 to n do if ru[i]=0 then begin inc(ta); f[i]:=true; q[ta]:=i; end; end; procedure topsort; var x:longint; begin top:=0; while he<ta do begin inc(he); x:=q[he]; inc(top); order[top]:=x; dec(ru[w[x]]); if (ru[w[x]]=0) and (not f[w[x]]) then begin inc(ta); f[w[x]]:=true; q[ta]:=w[x]; end; end; end; procedure main; var i,x,t:longint; begin he:=0; ta:=0; for i:=1 to n do if not f[i] then begin inc(ta); q[ta]:=i; f[i]:=true; t:=ta-1; sum:=a[i]; while he<ta do begin inc(he); x:=q[he]; if not f[w[x]] then begin inc(sum,a[w[x]]); f[w[x]]:=true; inc(ta); q[ta]:=w[x]; end else break; end; he:=t; while he<ta do begin inc(he); x:=q[he]; ans[x]:=sum; end; end; end; procedure print; var i:longint; begin for i:=top downto 1 do ans[order[i]]:=a[order[i]]+ans[w[order[i]]]; for i:=1 to n do writeln(ans[i]); end; begin init; topsort; main; print; end.