2016年2月26日 星期五

[HOJ 136][IOI 2007]Training (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解和code在這裡這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 136 - Training

Problem Statistics
Solved Member: 9  Submission: 28  User Tried: 9
Problem:
馬可(Mirko)和史拉可(Slavko)為了參加一年一度在克羅埃西亞(Coratia)舉行的雙人自行車馬拉松大賽正在加緊努力訓練。他們須要選擇一條路線(route)來訓練。

在他們的國家有 N 座城市與 M 條雙向道路(roads)。每一條道路連接兩個城市。但只有 N-1條道路是已被鋪築好的,其它的道路則是還沒被鋪築好的道路,幸好任兩座城市間都有一條用已鋪築好的道路路徑所連結。換句話說,這 N 座城市與 N-1 條已被鋪築好的條道路形成了一顆樹狀結構。

此外,每座城市最多可以是 10 條道路的端點。

訓練的路線可以從某一座城市開始,在經過數條道路後最後回到原來出發的城市。馬可和史拉可喜歡經過新的地點,所以他們訂了一項規則: 就是絕不經過相同的城市且絕不騎過相同的道路。訓練的路線可以在任何一座城市開始並且不須要經過每一座城市。

騎乘在後座是較輕鬆的,因為騎乘者可以因為前座騎乘者的關係而避開風。就因為如此,馬可和史拉可在每個城市會交換座位。為了確保他們能獲夠得相同的訓練量,他們想要選擇一條含有偶數條道路的路線。

馬可和史拉可的對手決定要封鎖某些尚未鋪築好的道路,讓他們無法找到一條滿足上述條件的路線。封鎖沒被鋪築好的道路須要付出一些代價(一個正整數) ,而已被鋪築好的道路是不可能被封鎖的。
Task:
寫一個程式,當給定城市與道路的描述後,找出封鎖道路使其無法滿足上述條件的訓練路徑之最小總代價。
Input:
輸入的第一行有兩個整數 N 與 M (2 ≤ N ≤ 1 000, N−1 ≤ M ≤ 5 000),分別代表城市的數目與道路的數目。

接下來的 M 行每一行都有三個整數 A 、B 和 C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000),用來表示一條道路。A 與 B 是不同的數字,表示直接由這條道路所連接的兩座城市。如果 C=0,表示該道路已被鋪築好了;否則該道路是尚未被鋪築過,而 C 代表封鎖此一條道路所需付出的代價。

每座城市最多可以是 10 條道路的端點,且兩座城市間絕對不會有一條以上的道路直接連接。
Output:
輸出一個整數,代表在上述問題描述中的最小總代價。
Sample Input:
SAMPLE A:
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1

SAMPLE B:
9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0
Sample Output:
SAMPLE A:
5

SAMPLE B:
48
HINT:


第一個例子中道路與城市的陳列。已被鋪築好的道路是以粗體的邊表示。


對於馬可和史拉可來說,共有5個可能的路線。如果邊1-3、 3-5 和2-5 被封鎖, 則馬可和史拉可將會不能使用5個路線中的任何一個。封鎖這三個邊的代價是5。

只封鎖兩個邊,像是2-4 和 2-5,也是可以的,但這樣會導致較高的代價,6 。
Source:
IOI 2007
Problem Setter
Nekosyndrome
Testdata:
TestTimeMemoryScore
0-1500ms65536kb
0-2500ms65536kb
1-1500ms65536kb9
1-2500ms65536kb
2-1500ms65536kb9
2-2500ms65536kb
3-1500ms65536kb9
3-2500ms65536kb
4-1500ms65536kb9
4-2500ms65536kb
5-1500ms65536kb9
5-2500ms65536kb
6-1500ms65536kb9
6-2500ms65536kb
7-1500ms65536kb9
7-2500ms65536kb
8-1500ms65536kb9
8-2500ms65536kb
8-3500ms65536kb
9-1500ms65536kb9
9-2500ms65536kb
9-3500ms65536kb
10-1500ms65536kb9
10-2500ms65536kb
10-3500ms65536kb
10-4500ms65536kb
11-1500ms65536kb10
11-2500ms65536kb
11-3500ms65536kb
11-4500ms65536kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原