1698 . Problem H 神殿裡的觸手
TopCoder
Tags
Description
海鞘對於草甘的精神狀況束手無策，便帶著草甘來到了古墨西哥神殿。
哪知海鞘一打開神殿的正門，便有一條巨大的觸手竄出，差點就要把海鞘捲走。
海鞘向當地村人打聽情報，才知道原來21年前這座神殿莫名出現了一隻大觸手，
使得想要進去探勘考古的烏龜提心吊膽。
這座神殿是由N間房間和M條雙向走廊所構成，每條走廊都有長度且兩間房間之間可能有不只一條走廊連接。
傳說中觸手總共佔領了N-1條走道，使得牠恰好能自由來往每間房間。
而且，觸手佔領的走道長度總和是所有可能佔領方案中最小的。
海鞘一聽大喜，這不就是最小生成樹(MST)嗎！
這樣就可以知道該避開哪些走廊了，但仔細想想才發現不對：最小生成樹並不唯一！
他只能找到一些走廊是無論如何都會被觸手佔領的。
無魚蝦也好，海鞘需要你告訴他有哪些走廊絕對會被觸手所佔領。
Input Format
輸入第一行有兩個數字N, M，表示房間數量跟走廊數量。(房間編號)
接下來有M行，每行有三個數字Ai, Bi, Ci，表示第i條走廊連接Ai, Bi，長度為Ci。
保證N ≤ 100,000，M ≤ 400,000，Ci可以用32位元有號整數貯存。
Output Format
輸出包含兩行，第一行是一定會被觸手佔領的走廊個數。
第二行由小到大輸出每條走廊編號，以空白作分隔。
如果沒有任何走廊，第二行請輸出單一一個"0"。
Sample Input 1
5 6
1 2 10
2 3 10
3 4 5
4 5 5
3 5 5
1 5 100
1 2 10
2 3 10
3 4 5
4 5 5
3 5 5
1 5 100
Sample Output 1
2
1 2
1 2
Hints
範例中有三種可能觸手：選擇走廊{1, 2, 3, 4}或{1, 2, 3, 5}或{1, 2, 4, 5}。
Problem Source
原TIOJ1698 / ABCLS Contest, Problem H
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |