HDU

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1000+10;
 6 const int maxm=1000+10;
 7 
 8 struct Edge
 9 {
10     int u,v,dist;
11     Edge(){}
12     Edge(int u,int v,int d):u(u),v(v),dist(d){}
13     bool operator<(const Edge &rhs)const
14     {
15         return dist<rhs.dist;
16     }
17 };
18 
19 struct Kruskal
20 {
21     int n,m;
22     Edge edges[maxm];
23     int fa[maxn];
24     int findset(int x){ return fa[x]==-1?x: fa[x]=findset(fa[x]); }
25 
26     void init(int n)
27     {
28         this->n=n;
29         m=0;
30         memset(fa,-1,sizeof(fa));
31     }
32 
33     void AddEdge(int u,int v,int dist)
34     {
35         edges[m++]=Edge(u,v,dist);
36     }
37 
38     int kruskal()
39     {
40         int sum=0,cnt=0;
41         sort(edges,edges+m);
42 
43         for(int i=0;i<m;i++)
44         {
45             int u=edges[i].u, v=edges[i].v;
46             if(findset(u)  != findset(v))
47             {
48                 sum +=edges[i].dist;
49                 fa[findset(u)] = findset(v);
50                 if(++cnt>=n-1) return sum;
51             }
52         }
53         return -1;
54     }
55 }KK;
56 
57 int main()
58 {
59     int n,m;
60     while(scanf("%d",&m)==1&&m)
61     {
62         scanf("%d",&n);
63         KK.init(n);
64         while(m--)
65         {
66             int u,v,d;
67             scanf("%d%d%d",&u,&v,&d);
68             KK.AddEdge(u,v,d);
69         }
70         int ans = KK.kruskal();
71         if(ans==-1) printf("?
");
72         else printf("%d
",ans);
73     }
74     return 0;
75 }
View Code