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
.
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
