1
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct cesta {
int w;
int x;
int y;
};
int primerjaj_ceste (const void * a, const void * b) {
const struct cesta * c = (const struct cesta *) a;
const struct cesta * d = (const struct cesta *) b;
return c->w - d->w;
}
void obisci (char * adj, int n, int x, char * obiskal) {
obiskal[x] = 1;
char * off = adj + x*n;
for (int i = 0; i < n; i++)
if (off[i] && !obiskal[i])
obisci(adj, n, i, obiskal);
}
int povezan (char * adj, int n) {
char * obiskal = calloc(n, sizeof *obiskal);
obisci(adj, n, 0, obiskal);
for (int i = 0; i < n; i++)
if (!obiskal[i]) {
free(obiskal);
return 0;
}
free(obiskal);
return 1;
}
int main (void) {
char buf[128];
fgets(buf, 128, stdin);
char * c = buf;
int n = strtol(c, &c, 10);
c++;
int m = strtol(c, &c, 10);
int i = m;
struct cesta * ceste = calloc(m, sizeof *ceste);
int skupen_w = 0;
char * adj = calloc(n*n, sizeof *adj);
while (i--) {
fgets(buf, 128, stdin);
c = buf;
ceste[i].x = strtol(c, &c, 10)-1;
ceste[i].y = strtol(++c, &c, 10)-1;
skupen_w += ceste[i].w = strtol(++c, &c, 10);
adj[n*ceste[i].x+ceste[i].y]++;
adj[n*ceste[i].y+ceste[i].x]++;
}
qsort(ceste, m, sizeof(struct cesta), primerjaj_ceste);
#ifdef xxx
for (int i = 0; i < m; i++)
printf("w: %d\tpovezava: %d\t%d\n", ceste[i].w, ceste[i].x, ceste[i].y);
#endif
int od_w = 0;
/*
if (!povezan(adj, n)) {
fprintf(stderr, "NI POVEZAN!\n");
for (int i = 0; i < n*n; i++) {
fprintf(stderr, "%d ", adj[i]);
if (!((i+1)%n))
fprintf(stderr, "\n");
}
}
*/
for (int i = m-1; i >= 0; i--) {
adj[n*ceste[i].x+ceste[i].y] = 0;
adj[n*ceste[i].y+ceste[i].x] = 0;
if (!povezan(adj, n)) {
adj[n*ceste[i].x+ceste[i].y]++;
adj[n*ceste[i].y+ceste[i].x]++;
} else {
od_w += ceste[i].w;
}
}
/*
fprintf(stderr, "skupen_w: %d\n", skupen_w);
for (int i = 0; i < m; i++) {
if (adj[n*ceste[i].x + ceste[i].y] == 0) {
fprintf(stderr, "x\n");
izbran_w += ceste[i].w;
adj[n*ceste[i].x + ceste[i].y]++;
adj[n*ceste[i].y + ceste[i].x]++;
}
if (povezan(adj, n)) {
fprintf(stderr, "POVEZAN!\n");
} else if (i == m-1)
fprintf(stderr, "NAPAKA!\n");
}
*/
printf("%d\n", od_w);
}
|
