50188. Minimum Spanning Tree, part II
難度：2.5/51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <stdio.h>
#include <stdlib.h>
#include "mstTA.h"
typedef struct{
int a;
int b;
int len;
} s_road;
int cmp(const void* aa, const void* bb){
s_road* a = (s_road*)aa;
s_road* b = (s_road*)bb;
#ifdef ADD
return a->len - b->len;
#endif
#ifdef REMOVE
return b->len - a->len;
#endif
}
int main(){
int n, m; scanf("%d %d", &n, &m);
s_road road[50];
for(int i = 0; i < m; i++){
scanf("%d %d %d", &road[i].a, &road[i].b, &road[i].len);
}
qsort(road, m, sizeof(s_road), cmp);
MSTTA mst;
initTA(&mst, n);
#ifdef ADD
int cnt = 0;
for(int i = 0; i < m; i++){
int a = road[i].a, b = road[i].b, len = road[i].len;
if(hasPathTA(&mst, a, b)) continue;
addRoadTA(&mst, a, b, len);
printf("%d %d %d\n", a, b, len);
cnt++;
if(cnt == n - 1) break;
}
#endif
#ifdef REMOVE
int cnt = m;
for(int i = 0; i < m; i++){
int a = road[i].a, b = road[i].b, len = road[i].len;
addRoadTA(&mst, a, b, len);
}
for(int i = 0; i < m; i++){
int a = road[i].a, b = road[i].b, len = road[i].len;
removeRoadTA(&mst, a, b);
if(connectedTA(&mst)){
printf("%d %d %d\n", a, b, len);
cnt--;
}
else{
addRoadTA(&mst, a, b, len);
}
if(cnt == n - 1) break;
}
#endif
}