kruskal 22936K 391MS C++ 
prim    15576K 391MS C++
我看DISCUSS上有同学说这个题目很容易看出是稠密图，用prim更优一点，可是我的两个版本怎么内存用了那么多啊。
我看有很多4000K的代码，怎么写啊
附上两个版本：
prim:
#include <iostream>
#include <climits>
using namespace std;

int dis[2001][2001],m;
char input[2001][7];

int current[2001];

void prim()
{
	int i,j;
	int len_min,index_min;
	int sum=0;

	for(i=0; i<m; i++)
	{
		current[i]=dis[0][i];
	}
	
	for(i=1; i<m; i++)
	{
		len_min=INT_MAX;
		for(j=1; j<m; j++)
		{
			if(current[j]>0 && current[j]<len_min)
			{
				len_min=current[j];
				index_min=j;
			}
		}
		sum+=len_min;
		current[j]=0;

		for(j=1; j<m; j++)
		{
			if(current[j]>0 && current[j]>dis[index_min][j])
			{
				current[j]=dis[index_min][j];
			}
		}
	}

	printf("The highest possible quality is 1/%d.\n",sum);
}

int main()
{
	int i,j,k;
	int d;

	while(scanf("%d",&m)&&m)
	{
		for(i=0; i<m; i++)
		{
			scanf("%s",input[i]);
			dis[i][i]=0;
			for(j=0; j<i; j++)
			{
				d=0;
				for(k=0; k<7; k++)
				{
					if(input[i][k]!=input[j][k])
					{
						d++;
					}
				}
				dis[i][j]=dis[j][i]=d;
			}
		}
		prim();
	}

	return 0;
}
krukal:
#include <iostream>
#include <algorithm>
using namespace std;

char input[2001][7];

int m,nEdge;
int parent[2001],rank[2001];

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;
	int dis;
	Edge(){;}
	Edge(int uu, int vv, int dd)
	{
		u=uu;
		v=vv;
		dis=dd;
	}
	bool operator < (const Edge e)
	{
		return dis<e.dis;
	}
}edge[2001*2001/2];

void kruskal()
{
	BCSet set;
	int i,sum=0;

	for(i=0; i<m; i++)
	{
		set.makeSet(i);
	}

	sort(edge,edge+nEdge);

	for(i=0; i<nEdge; i++)
	{
		if(set.findSet(edge[i].u) != set.findSet(edge[i].v))
		{
			set.unionSet(set.findSet(edge[i].u), set.findSet(edge[i].v));
			sum+=edge[i].dis;
		}
	}

	printf("The highest possible quality is 1/");
	printf("%d",sum);
	printf(".\n");
}

int main()
{
	int i,j,k;
	int dis;

	while(scanf("%d",&m) && m)
	{
		i=0;
		nEdge=0;

		for(i=0; i<m; i++)
		{
			scanf("%s",input[i]);
			for(j=0; j<i; j++)
			{
				dis=0;
				for(k=0; k<7; k++)
				{
					if(input[i][k] != input[j][k])
					{
						dis++;
					}
				}
				edge[nEdge].v=i;
				edge[nEdge].u=j;
				edge[nEdge++].dis=dis;
			}
		}
		kruskal();
	}

	return 0;
}

• Re:为什么我的prim仅仅比kruskal内存少点点，执行时间确相差无几，求大牛帮忙看看 (41) damacheng009 2010-08-04 04:04:07