2013-09-15 20:04
题目描述
有这样一个游戏，桌面上摆了N枚硬币，分别标号1-N，每枚硬币有一个分数C[i]与一个后继硬币T[i]。作为游戏参与者的你，可以购买一个名为mlj的小机器人，从任一个硬币处开始游戏，然后跳往该硬币的后继硬币T[i]，直到你要它停下来，经过每个硬币时，你可以选择是否捡起它。当某个mlj机器人停下来后将被扔掉，这时你可以选择结束游戏或再买一个mlj机器人继续游戏。
注意，每个硬币只能捡一次，而且你不能要求mlj跳向一个已被捡起的硬币或从一个已被捡起的硬币处开始游戏，因为那样会把mlj摔坏的。
Your Task
一开始你的得分是0，每购买一个mlj机器人将扣掉你M分，捡起一个硬币将得到对应的分数C[i]，请问如何使得分尽量高（游戏过程中分数可以为负）。
输入文件
第一行两个正整数 N M
接下来N行，每行两个正整数C[i] T[i]。
输出文件
一个整数，最大得分。
样例输入
4 2
1 3
2 3
1 4
1 3
样例输出
2
数据约定
30% N<=10
60% N<=300
100 N<=100000 1<=T[i]<=N
运算过程及结果均在Longint范围内
因为有N个点，N条边，且每个点都只有一个后继，所以可推知图中一定存在环，所以先用tarjan缩点，得到一颗上宽下窄的树（因为一个点只能有一个后继，而每个点可以成为好多点的后继），为了DP方便，缩点重新建图时，将边反向，这时得到了一颗多叉树，考虑到可能出现森林，所以用一个总根节点将每颗多叉树的根节点连接起来。
然后我们得到了一颗多叉树，问题转化成了树形DP，由题意可知，因为到一个硬币可以不捡，所以机器人的路径可以重合，那么设W(X)代表从X节点向下走可以取得的最大值，假设X有多个儿子，因为当前有一个机器人由上方走来到X节点，所以X节点的儿子中最大的不用X重新买机器人，剩下的儿子中，如果W(P)>M，就相当于在P儿子处再买一个机器人，那么更新W(X)值，W(X):=W(P)-M;
{
$m 500000000
}
//
By BLADEVIL
var
n, m :longint;
father :
array
[
0
..
200010
]
of
longint;
start :longint;
flag, fseq :
array
[
0
..
100010
]
of
boolean;
stack :
array
[
0
..
100010
]
of
longint;
tot :longint;
time :longint;
low, dfn :
array
[
0
..
100010
]
of
longint;
key :
array
[
0
..
100010
]
of
longint;
color :longint;
pre, last, other :
array
[
0
..
200010
]
of
longint;
l :longint;
mark :
array
[
0
..
200010
]
of
longint;
ans :longint;
function
min(a,b:longint):longint;
begin
if
a>b
then
min:=b
else
min:=
a;
end
;
procedure
connect(x,y:longint);
begin
inc(l);
pre[l]:
=
last[x];
last[x]:
=
l;
other[l]:
=
y;
end
;
procedure
dfs(x:longint);
var
cur :longint;
begin
inc(tot);
stack[tot]:
=
x;
flag[x]:
=
true;
fseq[x]:
=
true;
inc(time);
dfn[x]:
=
time;
low[x]:
=
time;
cur:
=
other[last[x]];
if
not
flag[cur]
then
begin
dfs(cur);
low[x]:
=
min(low[x],low[cur]);
end
else
if
fseq[cur]
then
low[x]:=
min(low[x],dfn[cur]);
cur:
=-
1
;
if
dfn[x]=low[x]
then
begin
inc(color);
while
cur<>x
do
begin
cur:
=
stack[tot];
dec(tot);
fseq[cur]:
=
false;
key[cur]:
=
color;
mark[color]:
=mark[color]+
mark[cur];
end
;
end
;
end
;
procedure
init;
var
i :longint;
x :longint;
p :longint;
begin
read(n,m); tot:
=
0
; color:=
n;
for
i:=
1
to
n
do
father[i]:=
i;
for
i:=
1
to
n
do
begin
read(mark[i],x);
connect(i,x);
father[x]:
=
i;
end
;
for
i:=
1
to
n
do
if
father[i]=i
then
start:=
i;
if
start=
0
then
inc(start);
dfs(start);
for
i:=
1
to
n
do
if
key[i]=
0
then
dfs(i);
for
i:=
1
to
n
do
begin
p:
=
other[last[i]];
if
key[i]<>key[p]
then
begin
connect(key[p],key[i]);
father[key[i]]:
=
key[p];
end
;
end
;
for
i:=n+
1
to
color
do
if
father[i]=
0
then
connect(color+
1
,i);
end
;
function
w(x:longint):longint;
var
p, q :longint;
i, j, maxx :longint;
sum :longint;
begin
q:
=
last[x];
j:
=
0
;
w:
=
0
;
w:
=w+
mark[x];
maxx:
=
0
;
while
q<>
0
do
begin
p:
=
other[q];
sum:
=
w(p);
if
sum>m
then
w:=w+sum-
m;
if
sum>maxx
then
maxx:=
sum;
q:
=
pre[q];
end
;
if
maxx<m
then
w:=w+maxx
else
w:=w+
m;
end
;
begin
assign(input,
'
coin.in
'
); reset(input);
assign(output,
'
coin.out
'
); rewrite(output);
init;
ans:
=w(color+
1
)-
m;
if
ans>
0
then
writeln(ans)
else
writeln(
0
);
close(input); close(output);
end
.
