168 . 鐵路拆除

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

20.0% (1/5)

Tags

ioicamp ioicamp-2022

Description

IOIC 國有 $n$ 個城市，而這 $n$ 個城市透過 $m$ 條鐵路互相連接，其中第 $i$ 條鐵路連接城市 $u_i$ 以及 $v_i$，並且是由第 $p_i$ 間地鐵公司所建構並營利。

由於疫情造成 IOIC 國經濟嚴重蕭條，政府決定拆除絕大多數的鐵路，只留下必要的鐵路使得所有的城市依然可以互相抵達。當然，隨意的拆除鐵路可能會引來地鐵公司的抱怨，因為地鐵公司最大的收入來源就是人們通勤時使用他們所營利的鐵路。因此，在最大化拆除鐵路數量的同時，政府還想儘可能的讓盡量多地鐵公司都能至少還有一條運行中的鐵路，以避免 IOIC 國的經濟情況更下低迷。

請你幫幫 IOIC 國，找出一組最佳的鐵路拆除方案吧！

Input Format

輸入的第一行有兩個正整數 $n, m$，代表城市以及鐵路的數量。

接著 $m$ 行，每行有三個正整數 $u_i, v_i, p_i$，代表第 $i$ 條鐵路的起訖城市以及所屬公司。

  • $1 \leq n \leq 5000$
  • $n - 1 \leq m \leq 30000$
  • $1 \leq u_i \neq v_i \leq n$
  • $1 \leq p_i \leq m$
  • 保證在未拆除鐵路的情況下，所有城市皆可以互相抵達

Output Format

請輸出兩行。

第一行請輸出一個正整數，代表最多能有幾家地鐵公司保有至少一條鐵路。

第二行請輸出 $n - 1$ 個以空白隔開且介於 $1$ 到 $m$ 之間的正整數 $e_1, e_2, \ldots, e_{n - 1}$，代表未拆除的鐵路編號。若有多組最佳解，請輸出任意一組即可。

Sample Input 1

6 7
1 2 1
1 3 2
2 3 5
2 4 4
4 5 3
4 6 2
5 6 4

Sample Output 1

5
1 3 4 5 6

Sample Input 2

3 3
1 2 1
2 3 1
1 3 1

Sample Output 2

1
1 2

Hints

Problem Source

IOICamp 2022 Day2 pH

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~28 $n, m \leq 20$ 10
3 0~59 $n \leq 50, m \leq 300$ 35
4 0~92 $n \leq 500, m \leq 3000$ 45
5 0~126 無額外限制 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3 4 5
1 3000 262144 65536 1 2 3 4 5
2 3000 262144 65536 2 3 4 5
3 3000 262144 65536 2 3 4 5
4 3000 262144 65536 2 3 4 5
5 3000 262144 65536 2 3 4 5
6 3000 262144 65536 2 3 4 5
7 3000 262144 65536 2 3 4 5
8 3000 262144 65536 2 3 4 5
9 3000 262144 65536 2 3 4 5
10 3000 262144 65536 2 3 4 5
11 3000 262144 65536 2 3 4 5
12 3000 262144 65536 2 3 4 5
13 3000 262144 65536 2 3 4 5
14 3000 262144 65536 2 3 4 5
15 3000 262144 65536 2 3 4 5
16 3000 262144 65536 2 3 4 5
17 3000 262144 65536 2 3 4 5
18 3000 262144 65536 2 3 4 5
19 3000 262144 65536 2 3 4 5
20 3000 262144 65536 2 3 4 5
21 3000 262144 65536 2 3 4 5
22 3000 262144 65536 2 3 4 5
23 3000 262144 65536 2 3 4 5
24 3000 262144 65536 2 3 4 5
25 3000 262144 65536 2 3 4 5
26 3000 262144 65536 2 3 4 5
27 3000 262144 65536 2 3 4 5
28 3000 262144 65536 2 3 4 5
29 3000 262144 65536 3 4 5
30 3000 262144 65536 3 4 5
31 3000 262144 65536 3 4 5
32 3000 262144 65536 3 4 5
33 3000 262144 65536 3 4 5
34 3000 262144 65536 3 4 5
35 3000 262144 65536 3 4 5
36 3000 262144 65536 3 4 5
37 3000 262144 65536 3 4 5
38 3000 262144 65536 3 4 5
39 3000 262144 65536 3 4 5
40 3000 262144 65536 3 4 5
41 3000 262144 65536 3 4 5
42 3000 262144 65536 3 4 5
43 3000 262144 65536 3 4 5
44 3000 262144 65536 3 4 5
45 3000 262144 65536 3 4 5
46 3000 262144 65536 3 4 5
47 3000 262144 65536 3 4 5
48 3000 262144 65536 3 4 5
49 3000 262144 65536 3 4 5
50 3000 262144 65536 3 4 5
51 3000 262144 65536 3 4 5
52 3000 262144 65536 3 4 5
53 3000 262144 65536 3 4 5
54 3000 262144 65536 3 4 5
55 3000 262144 65536 3 4 5
56 3000 262144 65536 3 4 5
57 3000 262144 65536 3 4 5
58 3000 262144 65536 3 4 5
59 3000 262144 65536 3 4 5
60 3000 262144 65536 4 5
61 3000 262144 65536 4 5
62 3000 262144 65536 4 5
63 3000 262144 65536 4 5
64 3000 262144 65536 4 5
65 3000 262144 65536 4 5
66 3000 262144 65536 4 5
67 3000 262144 65536 4 5
68 3000 262144 65536 4 5
69 3000 262144 65536 4 5
70 3000 262144 65536 4 5
71 3000 262144 65536 4 5
72 3000 262144 65536 4 5
73 3000 262144 65536 4 5
74 3000 262144 65536 4 5
75 3000 262144 65536 4 5
76 3000 262144 65536 4 5
77 3000 262144 65536 4 5
78 3000 262144 65536 4 5
79 3000 262144 65536 4 5
80 3000 262144 65536 4 5
81 3000 262144 65536 4 5
82 3000 262144 65536 4 5
83 3000 262144 65536 4 5
84 3000 262144 65536 4 5
85 3000 262144 65536 4 5
86 3000 262144 65536 4 5
87 3000 262144 65536 4 5
88 3000 262144 65536 4 5
89 3000 262144 65536 4 5
90 3000 262144 65536 4 5
91 3000 262144 65536 4 5
92 3000 262144 65536 4 5
93 3000 262144 65536 5
94 3000 262144 65536 5
95 3000 262144 65536 5
96 3000 262144 65536 5
97 3000 262144 65536 5
98 3000 262144 65536 5
99 3000 262144 65536 5
100 3000 262144 65536 5
101 3000 262144 65536 5
102 3000 262144 65536 5
103 3000 262144 65536 5
104 3000 262144 65536 5
105 3000 262144 65536 5
106 3000 262144 65536 5
107 3000 262144 65536 5
108 3000 262144 65536 5
109 3000 262144 65536 5
110 3000 262144 65536 5
111 3000 262144 65536 5
112 3000 262144 65536 5
113 3000 262144 65536 5
114 3000 262144 65536 5
115 3000 262144 65536 5
116 3000 262144 65536 5
117 3000 262144 65536 5
118 3000 262144 65536 5
119 3000 262144 65536 5
120 3000 262144 65536 5
121 3000 262144 65536 5
122 3000 262144 65536 5
123 3000 262144 65536 5
124 3000 262144 65536 5
125 3000 262144 65536 5
126 3000 262144 65536 5
Submit
Back to Top