http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2896
#include <stdio.h> #include <string.h> #include <stdlib.h> struct node { int u,v,w; }q[200001]; int bin[50001]; int n,m,ans; int cmp(const void *a,const void *b) { struct node *x; struct node *y; x = (struct node *)a; y = (struct node *)b; return x->w - y->w; } int find(int x) { int r,k,j; r = x; while(bin[r]!=r) r = bin[r]; j = x; while(j!=r) { k = bin[j]; bin[j] = r; j = k; } return r; } void kruskal() { int i; for(i = 1;i<=n;i++) { bin[i] = i; } for(i = 0;i<m;i++) { int uu = find(q[i].u); int vv = find(q[i].v); if(uu!=vv) { bin[uu] = vv; ans+=q[i].w; } } printf("%d ",ans); } int main() { int i,j; while(~scanf("%d%d",&n,&m)) { ans = 0; for(i = 0;i<m;i++) { scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w); } qsort(q,m,sizeof(q[0]),cmp); kruskal(); } return 0; }
对于kruskal 算法的理解 ：这个算法，我一直半知半解，知道现在才能够说明白，但也还不够熟练，谈谈我对这个算法的理解。
最小生成树的算法一共学了两种，分别是prim算法和kruskal算法，prim算法是我掌握的最好的算法之一，可或许因此对于prim算法过于依赖，对kruskal算法应用不熟练，导致很多题都不能AC ，现在重新学习一下kruskal算法，kruskal算法是一种加边的算法，适合点特别多的数据，kruskal算法应用并查集的知识，判断是否会形成回路，
还有就是结构体一级排序 两个重难点，
特别写一下cmp函数
int cmp(const void *a,const void *b)
{
struct node *x,*y;
x = （struct node *)a；
y = (struct node *)b; (括号不可少)
return x.w-y.w;
}
查找函数也是关键，krusal算法比较简单，可以遍历所有的边，进行判断。