Description
X先生来到了一个奇怪的国家旅行。这个国家有N个城市，每个城市均有且仅有一个机场，但是这机场所有航班只飞往一个城市。每个城市有一个游览价值，第i个城市的游览价值为A[i]。 现在他想知道，从第i个城市出发，并只坐飞机飞往下一个城市，游览价值之和最多是多少（一个城市游览多次只计算1次游览价值）
输入文件travel.in的第1行为一个正整数N。 第2行有N个非负整数A[i]，表示了每个城市的游览价值。 第3行有N个正整数F[i]，表示第i个城市的航班飞往的城市为F[i]，可能出现F[i] = i的情况。
Output
输出文件travel.out包括N行，第i行包含一个非负整数，表示从第i个城市出发游览价值之和的最大值为多少。
分析
我们可以发现在一个环上的点的价值相同。
所以，可以把一个环缩成一个点，价值为环上的点的价值和。(用tarjan·强连通分量)
然后，来个简简单单的递推就好了。
代码
const
maxn=
400100;
type
arr=
record
x,y:longint;
next:longint;
end;
var
value,f:
array[
0..maxn]
of longint;
memory:
array[
0..maxn]
of longint;
status:
array[
0..maxn]
of boolean;
dfn,low:
array[
0..maxn]
of longint;
sign:
array[
0..maxn]
of longint;
edge:
array[
0..maxn]
of arr;
ls:
array[
0..maxn]
of longint;
zhan:
array[
0..maxn]
of longint;
backup:
array[
0..maxn]
of longint;
top:longint;
number:longint;
n,m,nm:longint;
shu,shu1:longint;
procedure add(x,y:longint);
begin
m:=m+
1;
edge[m].x:=x;
edge[m].y:=y;
edge[m].next:=ls[x];
ls[x]:=m;
end;
procedure init;
var
i,j,k:longint;
begin
m:=
0;
nm:=
0;
fillchar(ls,sizeof(ls),
0);
readln(n);
for i:=
1 to n
do
read(value[i]);
readln;
for i:=
1 to n
do
begin
read(j);
add(i,j);
end;
end;
function min(x,y:longint):longint;
begin
if x>y
then exit(y)
else exit(x);
end;
procedure dfs(x:longint);
var
i,y:longint;
begin
inc(number);
inc(top);
shu:=shu+
1;
zhan[top]:=x;
dfn[x]:=number;
low[x]:=number;
i:=ls[x];
while i<>
0 do
begin
y:=edge[i].y;
if dfn[y]=
0
then
begin
dfs(y);
low[x]:=min(low[y],low[x]);
end
else
if not status[y]
then low[x]:=min(dfn[y],low[x]);
i:=edge[i].next;
end;
if dfn[x]=low[x]
then
begin
nm:=nm+
1;
repeat
sign[zhan[top]]:=nm;
status[zhan[top]]:=
true;
top:=top-
1;
until zhan[top+
1]=x;
end;
end;
procedure search(x:longint);
begin
shu1:=shu1+
1;
if status[x]
then exit;
status[x]:=
true;
search(f[x]);
memory[x]:=memory[f[x]]+value[x];
end;
procedure main;
var
i:longint;
begin
number:=
0;
for i:=
1 to n
do
if dfn[i]=
0 then dfs(i);
for i:=
1 to n
do
backup[sign[i]]:=backup[sign[i]]+value[i];
value:=backup;
for i:=
1 to m
do
with edge[i]
do
begin
if sign[y]<>sign[x]
then f[sign[x]]:=sign[y];
end;
fillchar(status,sizeof(status),
false);
for i:=
1 to n
do
begin
if not status[sign[i]]
then search(sign[i]);
writeln(memory[sign[i]]);
end;
end;
begin
init;
main;
end.
转载请注明原文地址: https://ju.6miu.com/read-1302941.html
