2569. 【NOIP2011模拟9.17】旅行 (Standard IO)

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个城市出发游览价值之和的最大值为多少。

Sample Input

8

5 4 3 2 1 1 1 1

2 3 1 1 2 7 6 8

Sample Output

12

12

12

14

13

2

2

1

对于20%的数据，N≤10； 对于40%的数据，N≤1000； 对于100%的数据，N≤200000，A[i]≤10000，F[i]≤N。

题解

这一题关键在于处理环的问题，因为题目限定，所有的点终结于环，有两种方案： 1：强连通分量（“太监”）缩点，把一个环变成一个点。 2：拓扑排序，把入度为0的去除，剩下的就是一个个环了。

代码

var a,b,f,x,y,c:array[1..200000] of longint; s:array[1..200000] of boolean; i,j,n,h,t,k,l,o,sum:longint; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do begin read(b[i]); inc(f[b[i]]); end; for i:=1 to n do if f[i]=0 then begin inc(t); s[i]:=true; x[t]:=i; end; while h<t do begin inc(h); k:=x[h]; inc(o); y[o]:=k; dec(f[b[k]]); if (f[b[k]]=0)and(s[b[k]]=false) then begin inc(t); s[b[k]]:=true; x[t]:=b[k]; end; end; h:=0;t:=0; for i:=1 to n do if s[i]=false then begin inc(t); x[t]:=i; s[i]:=true; l:=t-1; sum:=a[i]; while h<t do begin inc(h); k:=x[h]; if s[b[k]]=false then begin sum:=sum+a[b[k]]; s[b[k]]:=true; inc(t); x[t]:=b[k]; end else break; end; h:=l; while h<t do begin inc(h); k:=x[h]; c[k]:=sum; end; end; for i:=o downto 1 do c[y[i]]:=a[y[i]]+c[b[y[i]]]; for i:=1 to n do writeln(c[i]); end.