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[..] of longint;
start :longint;
flag, fseq :array[..] of boolean;
stack :array[..] of longint;
tot :longint;
time :longint;
low, dfn :array[..] of longint;
key :array[..] of longint;
color :longint;
pre, last, other :array[..] of longint;
l :longint;
mark :array[..] 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:=-;
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:=; color:=n;
for i:= to n do father[i]:=i;
for i:= to n do
begin
read(mark[i],x);
connect(i,x);
father[x]:=i;
end;
for i:= to n do if father[i]=i then start:=i;
if start= then inc(start);
dfs(start);
for i:= to n do if key[i]= then dfs(i);
for i:= 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+ to color do if father[i]= then connect(color+,i);
end;
function w(x:longint):longint;
var
p, q :longint;
i, j, maxx :longint;
sum :longint;
begin
q:=last[x];
j:=;
w:=;
w:=w+mark[x];
maxx:=;
while q<> 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+)-m;
if ans> then writeln(ans) else writeln();
close(input); close(output);
end.