HDU 1863 Kruskal求最小生成树

好久没写博客了写着玩的……

Kruskal这种东西离散都学过……

一句话……

添加当前图权值最小且构不成环的一条边直到连接所有点……

其他人好多Kruskal的模版肯定有比我的好的……

就是刷一波存在感……

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #define maxn 101
 4 
 5 using namespace std;
 6 
 7 int vis[maxn];
 8 int num,sum;
 9 
10 struct edge{
11     int a;
12     int b;
13     int value;
14 }p[maxn*maxn];
15 
16 int find_(int x){
17     int r=x;
18     while(r!=vis[r]){
19         r=vis[r];
20     }
21     return r;
22 }
23 
24 void Kruskal(int x,int y,int z){
25     int x1=find_(x);
26     int y1=find_(y);
27     if(x1!=y1){
28         vis[x1]=y1;
29         sum+=z;
30         num++;
31     }
32 }
33 
34 bool cmp(const edge &a, const edge &b){
35     return a.value < b.value;
36 }
37 
38 int main(){
39     int n,m,i;
40     while(~scanf("%d%d",&n,&m)&&n){
41         for(i=0;i<=m;i++)
42             vis[i]=i;
43         for(i=0;i<n;i++)
44             scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].value);
45         sum=0;
46         num=0;
47         sort(p,p+n,cmp);
48         for(i=0;i<n&&num<m-1;i++)
49             Kruskal(p[i].a,p[i].b,p[i].value);
50         if(num==m-1) printf("%d
",sum);
51         else printf("?
");
52     }
53     return 0;
54 }