最小生成树（Kruskal）

[c++]代码库

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

const int maxn = 5005;

struct Edge
{
	int u;
	int v;
	int val;
	bool operator < (const Edge &b)const
	{
		return val < b.val;
	}
}edge[maxn];

int n;
int father[105];

int find(int x)
{
	int r = x;
	while(r != father[r])
		r = father[r];
	int i = x,t;
	while(i != r)
	{
		t = father[i];
		father[i] = r;
		i = t;
	}
	return r;
}

void mix(int x,int y)
{
	int fx = find(x);
	int fy = find(y);
	if(fx != fy)
		father[fx] = fy;
}

int kruskal(int e)
{
	int ans = 0;
	int cnt = 0;
	for(int i = 0;i < e;i++)
	{
		if(find(edge[i].u) != find(edge[i].v))
		{
			cnt++;
			mix(edge[i].u,edge[i].v);
			ans += edge[i].val;
		}
		if(cnt == n-1)
			break;
	}
	return ans;
}
int main()
{

    while(scanf("%d",&n) != EOF && n)
    {
    	for(int i = 1;i <= n;i++)
	    	father[i] = i;
    	int e = n*(n-1)/2;
    	for(int i = 0;i < e;i++)
    	{
    		int is;
	    	scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val,&is);
	    	if(is)
	    		edge[i].val = 0;
	    }
	    sort(edge,edge+e);

	    printf("%d\n",kruskal(e));
    }
    return 0;
}

[源代码打包下载]