旅行

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

Hint

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

题解

题目的难点在于求环 因为每个点只有一个出度和入度，那么环是不可能向任意一点发出边的 照例跑一遍tarjan求强联通分量也就是环，缩点，顺便也把环上的权值缩在环的编号上 dfs一下找最大值，记忆化搜索优化一下 据说拓扑排序可以过，也许吧 c++极限数据会爆栈，调了半天也就放弃了 为数不多的过100行的程序，留念一下标个tag

Code

type edge=record x,y,next:longint; end; arr=array[0..200000]of edge; var n,m,t,maxE,maxG,ans:longint; comp,low,dfn,ass,ls,wx,s,w:array[0..200000]of longint; v:array[0..200000]of boolean; flag:boolean; e,g:arr; function min(x,y:longint):longint; begin min:=x; if y<x then min:=y; end; procedure add(var q:arr;var max:longint;x,y:longint); begin inc(max); q[max].x:=x; q[max].y:=y; q[max].next:=ls[x]; ls[x]:=max; end; procedure tarjan(x:longint); var i,y:longint; begin inc(t); dfn[x]:=t; low[x]:=t; inc(s[0]); s[s[0]]:=x; v[x]:=true; i:=ls[x]; while i>0 do begin if dfn[e[i].y]=0 then begin tarjan(e[i].y); low[x]:=min(low[e[i].y],low[x]); end else if v[e[i].y] then low[x]:=min(low[x],dfn[e[i].y]); i:=e[i].next; end; if dfn[x]=low[x] then begin inc(comp[0]); repeat y:=s[s[0]]; comp[y]:=comp[0]; wx[comp[0]]:=wx[comp[0]]+w[y]; v[y]:=false; dec(s[0]); until x=y; end; end; procedure dfs(dep:longint); var i:longint; begin if ass[dep]>0 then begin ans:=ans+ass[dep]; exit; end; ans:=ans+wx[dep]; i:=ls[dep]; while i>0 do begin dfs(e[i].y); i:=e[i].next; end; end; procedure print; var i:longint; begin for i:=1 to n do begin ans:=ass[comp[i]]; if ans=0 then dfs(comp[i]); writeln(ans); ass[comp[i]]:=ans; end; end; procedure main; var i:longint; begin for i:=1 to n do if dfn[i]=0 then tarjan(i); fillchar(ls,sizeof(ls),0); for i:=1 to maxE do if comp[e[i].x]<>comp[e[i].y] then add(g,maxG,comp[e[i].x],comp[e[i].y]); maxE:=maxG; e:=g; end; procedure init; var i,x,y:longint; begin readln(n); for i:=1 to n do read(w[i]); for i:=1 to n do begin read(x); add(e,maxE,i,x); end; end; begin init; main; print; end.