[2015.11.8|9图论]解题代码集合

HDOJ4081

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef struct Node{
 23     int x;
 24     int y;
 25     double w;
 26 }Node;
 27 
 28 const int maxn = 1111;
 29 int n, m, cnt;
 30 int pre[maxn], vis[maxn], peo[maxn];
 31 int x[maxn], y[maxn], p[maxn];
 32 Node e[maxn<<4];
 33 double mst;
 34 bool use[maxn<<4];
 35 
 36 bool cmp(Node n1, Node n2) {
 37     return n1.w < n2.w;
 38 }
 39 
 40 inline void clear() {
 41     memset(e, 0, sizeof(e));
 42     memset(x, 0, sizeof(x));
 43     memset(y, 0, sizeof(y));
 44     memset(p, 0, sizeof(p));
 45     memset(vis, 0, sizeof(vis));
 46     memset(use, 0, sizeof(use));
 47     memset(peo, 0, sizeof(peo));
 48     m = 0, cnt = 0, mst = 0;
 49 }
 50 
 51 inline void init() {
 52     for(int i = 0; i < maxn; i++) pre[i] = i;
 53 }
 54 
 55 int find(int x) {
 56     return x == pre[x] ? x : pre[x] = find(pre[x]);
 57 }
 58 
 59 bool unite(int x, int y) {
 60     x = find(x);
 61     y = find(y);
 62     if(x != y) {
 63         pre[x] = y;
 64         return 1;
 65     }
 66     return 0;
 67 }
 68 
 69 double dis(int i, int j) {
 70     return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
 71 }
 72 
 73 int main() {
 74     freopen("in", "r", stdin);
 75     int T;
 76     scanf("%d", &T);
 77     while(T--) {
 78         clear();
 79         scanf("%d", &n);
 80         for(int i = 0; i < n; i++) {
 81             scanf("%d %d %d", &x[i], &y[i], &p[i]);
 82         }
 83         for(int i = 0; i < n - 1; i++) {
 84             for(int j = i + 1; j < n; j++) {
 85                 e[m].x = i;
 86                 e[m].y = j;
 87                 e[m++].w = dis(i, j);
 88             }
 89         }
 90         init();
 91         sort(e, e+m, cmp);
 92         for(int i = 0; i < m; i++) {
 93             if(unite(e[i].x, e[i].y)) {
 94                 vis[cnt] = i;
 95                 mst += e[i].w;
 96                 peo[cnt] += p[e[i].x] + p[e[i].y];
 97                 cnt++;
 98             }
 99         }
100         double ans = -1;
101         for(int i = 0; i < n; i++) {
102             for(int j = 0; j < n; j++) {
103                 if(i != j) {
104                     ans = max(ans, (p[i]+p[j]) / (mst-dis(i,j)));
105                 }
106             }
107         }
108         printf("%.2lf
", ans);
109     }
110     return 0;
111 }

View Code

HDOJ4786

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef struct P {
 23     int u;
 24     int v;
 25     int w;
 26 }P;
 27 
 28 bool cmp1(P p1, P p2) {return p1.w < p2.w;}
 29 bool cmp2(P p1, P p2) {return p1.w > p2.w;}
 30 int A, B;
 31 
 32 const int maxn = 100010;
 33 int n, m, cnt;
 34 int pre[maxn];
 35 int fib[maxn];
 36 P e[maxn];
 37 
 38 int find(int x) {
 39     return x == pre[x] ? pre[x] : pre[x] = find(pre[x]);
 40 }
 41 
 42 bool unite(int x, int y) {
 43     x = find(x);
 44     y = find(y);
 45     if(x != y) {
 46         pre[x] = y;
 47         return 1;
 48     }
 49     return 0;
 50 }
 51 
 52 void init() {
 53     for(int i = 0; i < maxn; i++) {
 54         pre[i] = i;
 55     }
 56 }
 57 
 58 void clear() {
 59     init();
 60     memset(e, 0, sizeof(e));
 61     A = 0, B = 0;
 62     cnt = 0;
 63 }
 64 
 65 int main() {
 66     // freopen("in", "r", stdin);
 67     int T;
 68     fib[0] = 0, fib[1] = 1, fib[2] = 1;
 69     for(int i = 3; i <= 26; i++) {
 70         fib[i] = fib[i-1] + fib[i-2];
 71     }
 72     scanf("%d", &T);
 73     for(int _ = 1; _ <= T; _++) {
 74         printf("Case #%d: ", _);
 75         clear();
 76         scanf("%d %d", &n, &m);
 77         for(int i = 0; i < m; i++) {
 78             scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);
 79         }
 80         sort(e, e+m, cmp1);
 81         for(int i = 0; i < m; i++) {
 82             if(unite(e[i].u, e[i].v)) {
 83                 A += e[i].w;
 84                 cnt++;
 85             }
 86         }
 87         if(cnt != n - 1) printf("No
");
 88         else {
 89             init();
 90             sort(e, e+m, cmp2);
 91             for(int i = 0; i < m; i++) {
 92                 if(unite(e[i].u, e[i].v)) {
 93                     B += e[i].w;
 94                     cnt++;
 95                 }
 96             }
 97             int flag = 0;
 98             for(int i = 1; i <= 25; i++) {
 99                 if(fib[i] <= B && fib[i] >= A) {
100                     flag = 1;
101                     break;
102                 }
103             }
104             if(flag) printf("Yes
");
105             else printf("No
");
106         }
107     }
108 }

View Code

POJ2253

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 
23 const float inf = 2147483600;
24 const int maxn = 222;
25 int n;
26 bool vis[maxn];
27 float d[maxn];
28 float x[maxn],y[maxn];
29 
30 float dis(int a,int b) {
31     return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
32 }
33 
34 void dijkstra() {
35     for(int i = 0; i < n; i++) {
36         d[i] = inf;
37         vis[i] = 0;
38     }
39     d[0] = 0;
40     for(int i = 0; i < n; i++) {
41         int u = inf, ii;
42         for(int j = 0; j < n; j++) {        
43             if(!vis[j] && u > d[j]){
44                 u = d[j];
45                 ii = j;
46             }
47         }
48         vis[ii] = 1;
49         for(int j = 0; j < n; j++) {
50             d[j] = min(d[j], max(d[ii], dis(ii, j)));
51         }
52     }
53 }
54 
55 int main() {
56     // freopen("in", "r", stdin);
57     int _ = 0;
58     while(~scanf("%d", &n) && n){
59         for(int i = 0; i < n; i++) {
60             scanf("%f %f", &x[i], &y[i]);
61         }
62         dijkstra();
63         printf("Scenario #%d
", ++_);
64         printf("Frog Distance = %.3f

", d[1]);
65     }
66     return 0;
67 }

View Code

POJ3268

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef pair<int, int> PII;
23 const int inf = 100010;
24 const int maxn = 1111;
25 
26 typedef struct Edge {
27     int v;
28     int w;
29     Edge(int vv, int ww) : v(vv), w(ww) {}
30 };
31 
32 vector<Edge> G1[maxn], G2[maxn];
33 int n, m, x;
34 int u, v, w;
35 int d1[maxn], d2[maxn];
36 int ans;
37 
38 void dijkstra(int s, vector<Edge>* G, int* d) {
39     priority_queue<PII, vector<PII>, greater<PII> > pq;
40     for(int i = 1; i <= n; i++) d[i] = inf;
41     d[s] = 0;
42     pq.push(PII(0, s));
43     while(!pq.empty()) {
44         PII p = pq.top(); pq.pop();
45         int v = p.second;
46         if(d[v] < p.first) continue;
47         for(int i = 0; i < G[v].size(); i++) {
48             if(d[G[v][i].v] > d[v] + G[v][i].w) {
49                 d[G[v][i].v] = d[v] + G[v][i].w;
50                 pq.push(PII(d[G[v][i].v], G[v][i].v));
51             }
52         }
53     }
54 }
55 
56 int main() {
57     // freopen("in", "r", stdin);
58     scanf("%d %d %d", &n, &m, &x);
59     for(int i = 0; i < m; i++) {
60         scanf("%d %d %d", &u, &v, &w);
61         G1[u].push_back(Edge(v, w));
62     }
63     dijkstra(x, G1, d1);
64     for(int i = 1; i <= n; i++) {
65         for(int j = 0; j < G1[i].size(); j++) {
66             G2[G1[i][j].v].push_back(Edge(i, G1[i][j].w));
67         }
68     }
69     dijkstra(x, G2, d2);
70     ans = 0;
71     for(int i = 2; i <= n; i++) {
72         if(i == x) continue;
73         ans = max(ans, d1[i]+d2[i]);
74     }
75     printf("%d
", ans);
76     return 0;
77 }

View Code

AOJ0189

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 const int inf = 0x7f7f7f;
23 const int maxn = 111;
24 int G[maxn][maxn];
25 int d[maxn];
26 int n, m;
27 
28 void init() {
29     m = 0;
30     memset(d, 0, sizeof(d));
31     for(int i = 0; i < maxn; i++) {
32         for(int j = 0; j < maxn; j++) {
33             G[i][j] = G[j][i] = inf;
34         }
35         G[i][i] = 0;
36     }
37 }
38 
39 int main() {
40     // freopen("in", "r", stdin);
41     int u, v, w;
42     while(~scanf("%d", &n) && n) {
43         init();
44         for(int i = 0; i < n; i++) {
45             scanf("%d %d %d", &u, &v, &w);
46             if(w < G[u][v]) {
47                 G[u][v] = G[v][u] = w;
48             }
49             m = max(m, max(v, u) + 1);
50         }
51         for(int k = 0; k < m; k++) {
52             for(int i = 0; i < m; i++) {
53                 for(int j = 0; j < m; j++) {
54                     if(G[i][j] > G[i][k] + G[k][j]) {
55                         G[i][j] = G[i][k] + G[k][j];
56                     }
57                 }
58             }
59         }
60         for(int i = 0; i < m; i++) {
61             for(int j = 0; j < m; j++) {
62                 d[i] += G[i][j];
63             }
64         }
65         int ii = 0;
66         int ans = d[0];
67         for(int i = 1; i < m; i++) {
68             if(ans > d[i]) {
69                 ans = d[i];
70                 ii = i;
71             }
72         }
73         printf("%d %d
", ii, ans);
74     }
75 }

View Code

POJ1797

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 const int maxn = 1111;
23 const int inf = 0xffffff;
24 int d[maxn];
25 int G[maxn][maxn];
26 int vis[maxn];
27 int n, m;
28 
29 void init() {
30     memset(vis, 0, sizeof(vis));
31     memset(G, 0, sizeof(G));
32 }
33 
34 void dijkstra(int start) {
35     for(int i = 1; i <= n; i++) d[i] = G[1][i]; //最大承载量
36     for(int i = 1; i <= n; i++) {
37         int u = -1;
38         for(int j = 1; j <= n; j++) {
39             if(!vis[j]) {
40                 if(u == -1|| d[j] > d[u]) {
41                     u = j;
42                 }
43             }
44         }
45         vis[u] = 1;
46         for(int j = 1; j <= n; j++) {
47             if(!vis[j] && d[j] < min(d[u], G[u][j])) {
48                 d[j] = min(d[u], G[u][j]);
49             }
50         }
51     }
52 }
53 
54 int main() {
55     // freopen("in", "r", stdin);
56     int T;
57     int u, v, w;
58     scanf("%d", &T);
59     for(int _ = 1; _ <= T; _++) {
60         scanf("%d %d", &n, &m);
61         init();
62         while(m--) {
63             scanf("%d %d %d", &u, &v, &w);
64             G[u][v] = G[v][u] = w;
65         }
66         dijkstra(1);
67         printf("Scenario #%d:
%d

", _, d[n]);
68     }
69 }

View Code

POJ2031

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef struct Edge {
23     int u;
24     int v;
25     double w;
26 }E;
27 
28 typedef struct Ball {
29     double x;
30     double y;
31     double z;
32     double r;
33 }B;
34 
35 bool cmp(E e1, E e2) {
36     return e1.w < e2.w;
37 }
38 
39 const int maxn = 111;
40 int n, m;
41 int pre[maxn];
42 B b[maxn];
43 E e[maxn*maxn];
44 
45 inline void init() {
46     for(int i = 0; i < maxn; i++) {
47         pre[i] = i;
48     }
49     m = 0;
50 }
51 
52 int find(int x) {
53     return x == pre[x] ? x : pre[x] = find(pre[x]);
54 }
55 
56 bool unite(int x, int y) {
57     x = find(x);
58     y = find(y);
59     if(x != y) {
60         pre[x] = y;
61         return 1;
62     }
63     return 0;
64 }
65 
66 double dis(B b1, B b2) {
67     double res = double(sqrt((b1.x-b2.x)*(b1.x-b2.x)+(b1.y-b2.y)*(b1.y-b2.y)+(b1.z-b2.z)*(b1.z-b2.z))-b1.r-b2.r);
68     return res > 0 ? res : double(0);
69 }
70 
71 
72 int main() {
73     // freopen("in", "r", stdin);
74     while(~scanf("%d", &n) && n) {
75         init();
76         for(int i = 0; i < n; i++) {
77             scanf("%lf %lf %lf %lf", &b[i].x, &b[i].y, &b[i].z, &b[i].r);
78         }
79         for(int i = 0; i < n; i++) {
80             for(int j = 0; j < n; j++) {
81                 e[m].u = i;
82                 e[m].v = j;
83                 e[m++].w = dis(b[i], b[j]);
84             }
85         }
86         sort(e, e+m, cmp);
87         double mst = 0;
88         for(int i = 0; i < m; i++) {
89             if(unite(e[i].u, e[i].v)) {
90                 mst += e[i].w;
91             }
92         }
93         printf("%.3lf
", mst);
94     }
95     return 0;
96 }

View Code

POJ2421

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef struct E {
23     int u;
24     int v;
25     int w;
26 }E;
27 
28 const int maxn = 1111;
29 int n, m, q;
30 int a[maxn];
31 int pre[maxn];
32 E e[maxn*maxn];
33 
34 bool cmp(E e1, E e2) {
35     return e1.w < e2.w;
36 }
37 
38 void init() {
39     m = 0;
40     for(int i = 0; i < maxn; i++) {
41         pre[i] = i;
42     }
43 }
44 
45 int find(int x) {
46     return x == pre[x] ? x : pre[x] = find(pre[x]);
47 }
48 
49 bool unite(int x, int y) {
50     x = find(x);
51     y = find(y);
52     if(x != y) {
53         pre[x] = y;
54         return 1;
55     }
56     return 0;
57 }
58 
59 int main() {
60     int u, v;
61     // freopen("in", "r", stdin);
62     while(~scanf("%d", &n)) {        
63         init();
64         for(int i = 0; i < n; i++) {
65             for(int j = 0; j < n; j++) {
66                 scanf("%d", &v);
67                 e[m].u = i;
68                 e[m].v = j;
69                 e[m++].w = v;
70             }
71         }
72         scanf("%d", &q);
73         for(int i = 0; i < q; i++) {
74             scanf("%d %d", &u, &v);
75             int j = 0;
76             for(; j < m; j++) {
77                 if(e[j].u == u - 1 && e[j].v == v - 1) {
78                     break;
79                 }
80             }
81             e[j].w = 0;
82         }
83         sort(e, e+m, cmp);
84         int ans = 0;
85         for(int i = 0; i < m; i++) {
86             if(unite(e[i].u, e[i].v)) {
87                 ans += e[i].w;
88             }
89         }
90         printf("%d
", ans);
91     }
92     return 0;
93 }

View Code

POJ3255

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 
23 typedef struct E {
24     int w;
25     int v;
26     E() {}
27     E(int vv, int ww) : v(vv), w(ww) {}
28 }E;
29 
30 typedef pair<int, int> PII;
31 const int maxn = 5555;
32 const int inf = 0xffffff;
33 
34 priority_queue<PII, vector<PII>, greater<PII> > pq;
35 vector<E> e[maxn];
36 int d1[maxn], d2[maxn];
37 int n, m, u, v, w;
38 
39 void dijkstra(int s) {
40     for(int i = 0; i <= n; i++) d1[i] = d2[i] = inf;
41     while(!pq.empty()) pq.pop();
42     d1[s] = 0;
43     pq.push(PII(0, s));
44     while(!pq.empty()) {
45         PII cur = pq.top(); pq.pop();
46         w = cur.first;
47         v = cur.second;
48         if(d2[v] < w) continue;
49         for(int i = 0; i < e[v].size(); i++) {
50             int dd = w + e[v][i].w;
51             if(d1[e[v][i].v] > dd) {
52                 swap(d1[e[v][i].v], dd);
53                 pq.push(PII(d1[e[v][i].v], e[v][i].v));
54             }
55             if(d2[e[v][i].v] > dd && dd > d1[e[v][i].v]) {
56                 d2[e[v][i].v] = dd;
57                 pq.push(PII(d2[e[v][i].v], e[v][i].v));
58             }
59         }
60     }
61 }
62 
63 int main() {
64     // freopen("in", "r", stdin);
65     while(~scanf("%d %d", &n, &m)) {
66         for(int i = 0; i < m; i++) {
67             scanf("%d %d %d", &u, &v, &w);
68             e[u].push_back(E(v, w));
69             e[v].push_back(E(u, w));
70         }
71         dijkstra(1);
72         printf("%d
", d2[n]);
73     }
74 }

View Code

ZOJ1586

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef struct E {
23     int u;
24     int v;
25     int w;
26 }E;
27 
28 const int maxn = 1111;
29 int n, m, vv;
30 int a[maxn];
31 int pre[maxn];
32 E e[maxn*maxn];
33 
34 bool cmp(E e1, E e2) {
35     return e1.w < e2.w;
36 }
37 
38 void init() {
39     m = 0;
40     for(int i = 0; i < maxn; i++) {
41         pre[i] = i;
42     }
43 }
44 
45 int find(int x) {
46     return x == pre[x] ? x : pre[x] = find(pre[x]);
47 }
48 
49 bool unite(int x, int y) {
50     x = find(x);
51     y = find(y);
52     if(x != y) {
53         pre[x] = y;
54         return 1;
55     }
56     return 0;
57 }
58 
59 int main() {
60     // freopen("in", "r", stdin);
61     int T;
62     scanf("%d", &T);
63     while(T--) {
64         init();
65         scanf("%d", &n);
66         for(int i = 0; i < n; i++) {
67             scanf("%d", &a[i]);
68         }
69         for(int i = 0; i < n; i++) {
70             for(int j = 0; j < n; j++) {
71                 scanf("%d", &vv);
72                 e[m].u = i;
73                 e[m].v = j;
74                 e[m++].w = vv + a[i] + a[j];
75             }
76         }
77         // for(int i = 0; i < m; i++) {
78         //     printf("%d ", e[i].w);
79         // }
80         // printf("
");
81         sort(e, e+m, cmp);
82         int ans = 0;
83         for(int i = 0; i < m; i++) {
84             if(unite(e[i].u, e[i].v)) {
85                 ans += e[i].w;
86             }
87         }
88         printf("%d
", ans);
89     }
90     return 0;
91 }

View Code

HDOJ1233

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 typedef pair<int, int> PII; //w v
23 
24 typedef struct E{
25     int w;
26     int v;
27     E() {}
28     E(int vv, int ww) : v(vv), w(ww) {}
29 }E;
30 
31 const int inf = 0x7fffff;
32 const int maxn = 111111;
33 int n, nn;
34 int vis[maxn], d[maxn];
35 vector<E> e[maxn];
36 priority_queue<PII, vector<PII>, greater<PII> > pq;
37 
38 int prim(int s) {
39     int mst = 0;
40     memset(vis, 0, sizeof(vis));
41     for(int i = 0; i <= n; i++) d[i] = inf;
42     while(!pq.empty()) pq.pop();
43     d[s] = 0;
44     pq.push(PII(0, 1));
45     while(!pq.empty()) {
46         PII cur = pq.top(); pq.pop();
47         int w = cur.first;
48         int v = cur.second;
49         if(vis[v] || d[v] < w) continue;
50         vis[v] = 1;
51         mst += w;
52         for(int i = 0; i < e[v].size(); i++) {
53             int u = e[v][i].v;
54             int w = e[v][i].w;
55             if(!vis[u] && w < d[u]) {
56                 d[u] = w;
57                 pq.push(PII(d[u], u));
58             }
59         }
60     }
61     return mst;
62 }
63 
64 int main() {
65     // freopen("in", "r", stdin);
66     int u, v, w;
67     while(~scanf("%d", &n) && n) {
68         nn = n * (n - 1) / 2;
69         for(int i = 0; i <= n; i++) e[i].clear();
70         for(int i = 0; i < nn; i++) {
71             scanf("%d %d %d", &u, &v, &w);
72             e[u].push_back(E(v, w));
73             e[v].push_back(E(u, w));
74         }
75         printf("%d
", prim(1));
76     }
77 }

View Code