硬币问题 tarjan缩点+DP 莫涛

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

样例输出

数据约定

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.