镖局运镖——最小生成树（Kruskal算法）

镖局运镖——最小生成树（Kruskal算法）"/>

镖局运镖——最小生成树（Kruskal算法）

think:
1图的最小生成树(Kruskal算法)——(并查集++)

#include <stdio.h>
#include <stdlib.h>
int f[14];
struct node
{int u;int v;int w;
}ans[14];
void Init(int *a, int n)
{for(int i = 1; i <= n; i++){a[i] = i;}
}
int get_f(int x)
{if(f[x] == x)return x;else{f[x] = get_f(f[x]);return f[x];}
}
int merge(int a, int b)
{int t1 = get_f(a);int t2 = get_f(b);if(t1 != t2){f[t2] = t1;return 1;}elsereturn 0;
}
int cmp(const void *a, const void *b)
{struct node *c = (struct node *)a;struct node *d = (struct node *)b;if(c->w != d->w)return (c->w - d->w);
}
int main()
{int n, m, i, cnt, sum;while(scanf("%d %d", &n, &m) != EOF){cnt = sum = 0;Init(f, n);for(i = 0; i < m; i++){scanf("%d %d %d", &ans[i].u, &ans[i].v, &ans[i].w);}qsort(&ans[0], m, sizeof(ans[0]), cmp);for(i = 0; i < m; i++)//枚举每一条边{if(merge(ans[i].u, ans[i].v))//如果目前尚不连通，则选用这条边{cnt++;sum += ans[i].w;}if(cnt == n-1)//直到选用了n-1条边之后退出break;}printf("%d\n", sum);}return 0;
}