1004: 惠民工程 （2013年中南大学研究生复试机试 ）

 1 #include<iostream>
 2 #include<stdio.h> 
 3 #include<algorithm>
 4 using namespace std;
 5 /*要畅通，就必需要m-1条边，要使费用最小则尽量用权值最小的变，先对所有的边进行排序
 6 然后从小到大依次选择，判断该边是否可以加入此工程,判断的方法是使用并查集*/
 7 int n, m;
 8 int arr[105];
 9 struct node
10 {
11     int start, end, w;
12 }a[5010];
13 
14 int cmpare(node x, node y)
15 {
16     return x.w<y.w;
17 }
18 
19 int find(int x){
20     while(arr[x]!=x){
21         x=arr[x];
22     }
23     return x;
24 }
25 
26 int add(int x,int y){
27     int x1=find(x);
28     int y1=find(y);
29     if(x1!=y1){
30         arr[x1]=y1;
31         return 1;
32     }
33     return 0;
34 }
35 int main(){
36     while (scanf("%d%d", &m, &n) != EOF){
37         for (int i = 0; i < n; i++){
38             scanf("%d%d%d", &a[i].start, &a[i].end, &a[i].w);
39         }
40         sort(a, a + n, cmpare);
41         for (int i = 1; i <=m; i++){
42             arr[i] = i;
43         }
44         int num = 0;
45         int result = 0;
46         for (int i = 0; num < m - 1 && i < n; i++){
47             if (add(a[i].start,a[i].end)){
48                 num++;
49                 result += a[i].w;
50             }
51         }
52         if (num == m - 1){
53             printf("%d\n", result);
54         }
55         else{
56             printf("?\n");
57         }
58     }
59 }