K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
现将自己总结的kruskal算法模版粘贴如下：
前期发现自己的KMP错了！囧啊！
下面是HDU1102的代码，作为模版完全可以的！
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define read freopen("zx.in","r",stdin) #define write freopen("zx.out","w",stdout) #define N 110 typedef struct{ int p1,p2,cost; }Village; Village zx[N*N/2]; int fa[N],arr[N][N]; bool cmp(Village a,Village b) { return a.cost<b.cost; } int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); } int merge(int a,int b) { int xx=find(a), yy=find(b); if(xx==yy) return 0; else fa[yy]=xx; return 1; } int main() { //read, write; int num,mnum,a,b; while(scanf("%d",&num)!=EOF) { for(int i=1;i<=num;i++) fa[i]=i; for(int i=1;i<=num;i++) for(int j=1;j<=num;j++) scanf("%d",&arr[i][j]); int k=0; for(int i=1;i<=num;i++) { for(int j=i+1;j<=num;j++) { k++; zx[k].p1=i, zx[k].p2=j, zx[k].cost=arr[i][j]; } } sort(zx+1,zx+1+k,cmp); //for(int i=1;i<=k;i++) printf("%d ",zx[i].cost); printf("/n"); scanf("%d",&mnum); for(int i=1;i<=mnum;i++) { scanf("%d%d",&a,&b); int x=find(a), y=find(b); if(x!=y) fa[y]=x; } int sum=0; for(int i=1;i<=k;i++) { if(merge(zx[i].p1,zx[i].p2)) { sum+=zx[i].cost; } } printf("%d/n",sum); } return 0; }
