修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm
Submit Ranklist
第一個例子中道路與城市的陳列。已被鋪築好的道路是以粗體的邊表示。
對於馬可和史拉可來說，共有5個可能的路線。如果邊1-3、 3-5 和2-5 被封鎖， 則馬可和史拉可將會不能使用5個路線中的任何一個。封鎖這三個邊的代價是5。
只封鎖兩個邊，像是2-4 和 2-5，也是可以的，但這樣會導致較高的代價，6 。
Problem : 136 - Training
Problem Statistics
Solved Member: 9 Submission: 28 User Tried: 9Statement:
馬可(Mirko)和史拉可(Slavko)為了參加一年一度在克羅埃西亞(Coratia)舉行的雙人自行車馬拉松大賽正在加緊努力訓練。他們須要選擇一條路線(route)來訓練。
在他們的國家有 N 座城市與 M 條雙向道路(roads)。每一條道路連接兩個城市。但只有 N-1條道路是已被鋪築好的，其它的道路則是還沒被鋪築好的道路，幸好任兩座城市間都有一條用已鋪築好的道路路徑所連結。換句話說，這 N 座城市與 N-1 條已被鋪築好的條道路形成了一顆樹狀結構。
此外，每座城市最多可以是 10 條道路的端點。
訓練的路線可以從某一座城市開始，在經過數條道路後最後回到原來出發的城市。馬可和史拉可喜歡經過新的地點，所以他們訂了一項規則: 就是絕不經過相同的城市且絕不騎過相同的道路。訓練的路線可以在任何一座城市開始並且不須要經過每一座城市。
騎乘在後座是較輕鬆的，因為騎乘者可以因為前座騎乘者的關係而避開風。就因為如此，馬可和史拉可在每個城市會交換座位。為了確保他們能獲夠得相同的訓練量，他們想要選擇一條含有偶數條道路的路線。
馬可和史拉可的對手決定要封鎖某些尚未鋪築好的道路，讓他們無法找到一條滿足上述條件的路線。封鎖沒被鋪築好的道路須要付出一些代價(一個正整數) ，而已被鋪築好的道路是不可能被封鎖的。
在他們的國家有 N 座城市與 M 條雙向道路(roads)。每一條道路連接兩個城市。但只有 N-1條道路是已被鋪築好的，其它的道路則是還沒被鋪築好的道路，幸好任兩座城市間都有一條用已鋪築好的道路路徑所連結。換句話說，這 N 座城市與 N-1 條已被鋪築好的條道路形成了一顆樹狀結構。
此外，每座城市最多可以是 10 條道路的端點。
訓練的路線可以從某一座城市開始，在經過數條道路後最後回到原來出發的城市。馬可和史拉可喜歡經過新的地點，所以他們訂了一項規則: 就是絕不經過相同的城市且絕不騎過相同的道路。訓練的路線可以在任何一座城市開始並且不須要經過每一座城市。
騎乘在後座是較輕鬆的，因為騎乘者可以因為前座騎乘者的關係而避開風。就因為如此，馬可和史拉可在每個城市會交換座位。為了確保他們能獲夠得相同的訓練量，他們想要選擇一條含有偶數條道路的路線。
馬可和史拉可的對手決定要封鎖某些尚未鋪築好的道路，讓他們無法找到一條滿足上述條件的路線。封鎖沒被鋪築好的道路須要付出一些代價(一個正整數) ，而已被鋪築好的道路是不可能被封鎖的。
Task:
寫一個程式，當給定城市與道路的描述後，找出封鎖道路使其無法滿足上述條件的訓練路徑之最小總代價。
Input:Output:
輸入的第一行有兩個整數 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 條道路的端點，且兩座城市間絕對不會有一條以上的道路直接連接。
接下來的 M 行每一行都有三個整數 A 、B 和 C (1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000)，用來表示一條道路。A 與 B 是不同的數字，表示直接由這條道路所連接的兩座城市。如果 C=0，表示該道路已被鋪築好了；否則該道路是尚未被鋪築過，而 C 代表封鎖此一條道路所需付出的代價。
每座城市最多可以是 10 條道路的端點，且兩座城市間絕對不會有一條以上的道路直接連接。
輸出一個整數，代表在上述問題描述中的最小總代價。
Sample Input:Sample Output:
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
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 A:
5
SAMPLE B:
48
5
SAMPLE B:
48
HINT:
第一個例子中道路與城市的陳列。已被鋪築好的道路是以粗體的邊表示。
對於馬可和史拉可來說，共有5個可能的路線。如果邊1-3、 3-5 和2-5 被封鎖， 則馬可和史拉可將會不能使用5個路線中的任何一個。封鎖這三個邊的代價是5。
只封鎖兩個邊，像是2-4 和 2-5，也是可以的，但這樣會導致較高的代價，6 。
Source:
IOI 2007Problem Setter
NekosyndromeTestdata:
| Test | Time | Memory | Score |
|---|---|---|---|
| 0-1 | 500ms | 65536kb | |
| 0-2 | 500ms | 65536kb | |
| 1-1 | 500ms | 65536kb | 9 |
| 1-2 | 500ms | 65536kb | |
| 2-1 | 500ms | 65536kb | 9 |
| 2-2 | 500ms | 65536kb | |
| 3-1 | 500ms | 65536kb | 9 |
| 3-2 | 500ms | 65536kb | |
| 4-1 | 500ms | 65536kb | 9 |
| 4-2 | 500ms | 65536kb | |
| 5-1 | 500ms | 65536kb | 9 |
| 5-2 | 500ms | 65536kb | |
| 6-1 | 500ms | 65536kb | 9 |
| 6-2 | 500ms | 65536kb | |
| 7-1 | 500ms | 65536kb | 9 |
| 7-2 | 500ms | 65536kb | |
| 8-1 | 500ms | 65536kb | 9 |
| 8-2 | 500ms | 65536kb | |
| 8-3 | 500ms | 65536kb | |
| 9-1 | 500ms | 65536kb | 9 |
| 9-2 | 500ms | 65536kb | |
| 9-3 | 500ms | 65536kb | |
| 10-1 | 500ms | 65536kb | 9 |
| 10-2 | 500ms | 65536kb | |
| 10-3 | 500ms | 65536kb | |
| 10-4 | 500ms | 65536kb | |
| 11-1 | 500ms | 65536kb | 10 |
| 11-2 | 500ms | 65536kb | |
| 11-3 | 500ms | 65536kb | |
| 11-4 | 500ms | 65536kb |
NeoHOJ — The new era of HOJ
頁面讀取時間: 0.0068 秒，使用記憶體: 0.46MB 。
GitHub