hud3371 Connect the Cities 简单最小生成树

 1 //我看过Discuss说不能用克鲁斯卡尔因为有很多边
 2 //但是只能用G++过，C++的确超时
 3 #include <stdio.h>  
 4 #include <string.h>  
 5 #include <algorithm>  
 6 using namespace std;
 7 
 8 struct node
 9 {
10     int a, b, cost;
11 }c[30000];
12 int fa[505];
13 
14 void init(int n)
15 {
16     for (int i = 1; i <= n; i++)
17         fa[i] = i;
18 }
19 
20 bool cmp(node x, node y)
21 {
22     return x.cost<y.cost;
23 }
24 
25 int find(int x)
26 {
27     if (fa[x] != x) fa[x] = find(fa[x]);
28     return fa[x];
29 }
30 
31 int main()
32 {
33     int n, k, m, ncase;
34     scanf("%d", &ncase);
35     while (ncase--)
36     {
37         scanf("%d %d %d", &n, &k, &m);
38         init(n);    //初始化
39         for (int i = 0; i<k; i++)
40             scanf("%d %d %d", &c[i].a, &c[i].b, &c[i].cost);
41         for (int i = 1; i <= m; i++)
42         {
43             int x, pos, pos1;
44             scanf("%d %d", &x, &pos);
45             for (int j = 1; j<x; j++)
46             {
47                 scanf("%d", &pos1);
48                 c[k].a = pos, c[k].b = pos1, c[k].cost = 0;
49                 pos = pos1;
50                 k++;
51             }
52         }
53 
54         sort(c, c + k, cmp);
55         int sum = 0;
56         for (int i = 0; i<k; i++)
57         {
58             int x = find(c[i].a);
59             int y = find(c[i].b);
60             if (x != y)
61                 sum += c[i].cost, fa[x] = y;
62         }
63 
64         int count = 0;
65         for (int i = 1; i <= n; i++)
66         if (fa[i] == i)
67             count++;
68 
69         if (count != 1)
70             printf("-1
");
71         else
72             printf("%d
", sum);
73     }
74     return 0;
75 }