昨晚用prim过了，但是kruskal一直ＷＡ，百思不得其解，今天在网上找了若干版本，发现大体思路一样，中午的时候有种砸笔记本的冲动，睡了一觉后突然找到了ＢＵＧ，nEgde每次都没有清0.......
   太阳啊......
   啥也不说了，上了一个AC的版本：
#include <iostream>
#include <algorithm>
using namespace std;

int m,nEdge;
int parent[200]={0},rank[200]={0};

struct BCSet
{
	void makeSet(int i)
	{
		parent[i]=i;
		rank[i]=1;
	}
	int findSet(int i)
	{
		if(parent[i]!=i)
		{
			parent[i] = findSet(parent[i]);
		}
		return parent[i];	
	}
	void unionSet(int i, int j)
	{
		if(rank[i]>rank[j])
		{
			parent[j]=i;
		}
		else if(rank[i]<rank[j])
		{
			parent[i]=j;
		}
		else
		{
			rank[j]++;
			parent[i]=j;
		}
	}
};

struct Edge
{
	int u,v,d;
	Edge(){;}
	Edge(int uu, int vv, int dd)
	{
		u = uu;
		v = vv;
		d = dd;
	}
	bool operator < (const Edge e)
	{
		return d < e.d;
	}
}edge[200*200];

void kruskal()
{
	BCSet b;
	int i,len=0;

	for(i=0; i<m; i++)
	{
		b.makeSet(i);
	}
	sort(edge,edge+nEdge);
	for(i=0; i<nEdge; i++)
	{
		if(b.findSet(edge[i].u) != b.findSet(edge[i].v))
		{
			b.unionSet(b.findSet(edge[i].u), b.findSet(edge[i].v));
			len += edge[i].d;
		}
	}
	printf("%d\n",len);
}

int main()
{
	int i,j;
        //nEdge=0; 一开始写在这里，杯具了很久
	while(scanf("%d", &m)!=EOF)
	{
                //粗心害死人啊
		nEdge=0;
		for(i=0; i<m; i++)
		{
			for(j=0; j<m; j++)
			{
				if(j<=i-1)
				{
					edge[nEdge].u=i;
					edge[nEdge].v=j;
					scanf("%d",&edge[nEdge++].d);
				}
				else
				{
					scanf("%*d");
				}
			}
		}
		kruskal();
	}

	return 0;
}
   

• 发得倒挺快. (0) lijinwu 2010-04-07 13:56:02