HNOI2017模擬試
公路建設(shè)（road.pas）（1s 64m）
a國是一個(gè)新興的國家，有n個(gè)城市，分別編號為1,2.3…n。政府想大搞公路建設(shè)，提供了優(yōu)惠政策：對于每一個(gè)投資方案的預(yù)計(jì)總費(fèi)用，政府負(fù)擔(dān)50%，并且允許投資的公司對過往的汽車收取連續(xù)5年的養(yǎng)路費(fèi)。世界各地的大公司紛紛投資，并提出了自己的建設(shè)方案，他們的投資方案包括這些內(nèi)容：公路連接的兩座城市的編號，預(yù)計(jì)的總費(fèi)用（假設(shè)他們的預(yù)計(jì)總是準(zhǔn)確的）。
你作為a國公路規(guī)劃局的總工程師，有權(quán)利決定每一個(gè)方案是否接受。但是政府給你的要求是：
（1）要保證各個(gè)城市之間都有公路直接或間接相連。
（2）因?yàn)槭切屡d國家，政府的經(jīng)濟(jì)實(shí)力還不強(qiáng)。政府希望負(fù)擔(dān)最少的費(fèi)用。
因?yàn)榇蠊静⒉皇峭瑫r(shí)提出方案，政府希望每接到一個(gè)方案，就可以知道當(dāng)前需要負(fù)擔(dān)的最小費(fèi)用和接受的投資方案，以便隨時(shí)開工。關(guān)于你給投資公司的回復(fù)可以等到開工以后再給。注意：a國一開始是沒有公路的。我們設(shè)定a國的城市數(shù)目n≤500，投資的方案總數(shù)m≤。
【輸入】
輸入文件名：road.in
第1行有兩個(gè)數(shù)字：n、m
第2行到第m+1行給出了各個(gè)投資方案，第i行的方案編號為i-1
編號小的方案先接到，一個(gè)方案占一行，每行有3個(gè)數(shù)字，分別是連接的兩個(gè)城市編號a、b，和投資的預(yù)計(jì)總費(fèi)用cost。
【輸出】
輸出文件名：road.out
輸出文件共有m行。
每一行的第一個(gè)數(shù)字是當(dāng)前政府需要負(fù)擔(dān)的最少費(fèi)用（保留1位小數(shù)），后面是x個(gè)數(shù)字，表示當(dāng)前政府接受的方案的編號，不要求從小到大排列。但如果此時(shí)接受的所有投資方案不能保證政府的第一條要求，那么這一行只有一個(gè)數(shù)字0
【樣例】
road.in road.out
3 5
1 2 4
1 3 4
2 3 4
1 3 2
1 2 2 0
4.00 1 2
4.00 1 2
3.00 1 4
2.00 4 5
游戲（game.pas 1s 64m）
noixx公司最近推出了一款新的坦克游戲。在游戲中，你將操縱一輛坦克，在一個(gè)nm的區(qū)域中完成一項(xiàng)任務(wù)。在此的區(qū)域中，將會有許多可攻擊的目標(biāo)，而你每摧毀這樣的一個(gè)目標(biāo)，就將獲得與目標(biāo)價(jià)值相等的分?jǐn)?shù)。只有獲得了最高的分?jǐn)?shù)，任務(wù)才算完成。同時(shí)，為了增加游戲的真實(shí)性和難度，該游戲還做了以下的限制：
第一， 坦克有射程r的限制。為方便計(jì)算，射程r規(guī)定為：若坦克位于(x,y)格，則它可攻擊的目標(biāo)(x1,y1)必須滿足|x-x1|,|y-y1|∈[0,r]。
第二， 對坦克完成任務(wù)的時(shí)間有嚴(yán)格限制，規(guī)定為t秒。其中，坦克每進(jìn)行一次移動都需1秒的時(shí)間，每攻擊一個(gè)目標(biāo)也需1秒的時(shí)間。時(shí)間一到t秒，便對此次任務(wù)進(jìn)行記分。
第三， 坦克最初位于左上角，且移動方向只準(zhǔn)是向右或向下，每次只允許移動一格。
在以上的限制條件下，要完成該任務(wù)便成為了一件很難事情。因此，你必須為此編寫一個(gè)程序，讓它助你完成這個(gè)艱巨的任務(wù)。
【輸入】輸入文件：input.txt
第一行右四格整數(shù)n、m、r、t，分別表示區(qū)域的長、寬，以及射程和完成任務(wù)時(shí)間。
接下來n行是一格nm的矩陣，對應(yīng)每個(gè)位置上目標(biāo)的價(jià)值。1≤n、m≤500，1≤r≤100，1≤t≤2500。
【輸出】輸出文件：output.txt
輸出文件僅一個(gè)數(shù)max，即該任務(wù)中可得到的最高分?jǐn)?shù)。
【樣例】
輸入文件input.txt為：
5 5 2 7
0 5 0 0 4
0 0 0 0 2
0 0 0 0 0
0 0 0 0 0
5 0 3 0 11
輸出文件output.txt為：