用了prim的，在build函数中处理，但是还是超时，本地处理700个数据花了3s，大部分时间像是在处理输入输出
#include <iostream>
#include <string.h>
using namespace std;
#define  GetDisDB(x0,y0,x1,y1) ((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))
#define  Max  751
typedef struct
{
	int x,y;
}Point;

int HashConn[Max][Max];
int Map[Max][Max];
int SetConn[Max];
int ConnEndIndex;
int SetLeft[Max];
int LeftEndIndex;

Point Value[Max];

void SetZero(int a,int b)
{
	Map[a][b] = 0;
	Map[b][a] = 0;
}

void RemoveIndexFromLeft(int index)
{
	SetLeft[index] = 0;
	LeftEndIndex--;
}

void AddIndexToSetConn(int v)
{
	ConnEndIndex++;
	SetConn[ConnEndIndex] = v;
}

void Build(int n)
{
	int a,b,i,j,v;
	int index = 0;
	int curi,curj;

	while(LeftEndIndex)
	{
		a = b = 0;
		v = 0x0FFFFFFF;
		
		for(i= 1;i<=ConnEndIndex;i++)
			for(j=1;j<=n;j++)
			{
				if(SetLeft[j])
				{
					curi = SetConn[i];
					curj = SetLeft[j];
			 
					if((Map[curi][curj]<v))	
					{
						a = curi;
						b = curj;
						v = Map[curi][curj];
						index = j;
					}
				}
				
			}
		if(!HashConn[a][b])	cout<<a<<" "<<b<<endl;	
		AddIndexToSetConn(b);
		RemoveIndexFromLeft(index);
	
	}
}


int main()
{
	int i,j,n,p,a,b;
	int v,x,y;

	(cin>>n);
	{
		memset(Map,0,sizeof(int)*Max*Max);
		memset(SetConn,0,Max*sizeof(int));
		memset(SetLeft,0,Max*sizeof(int));
		memset(Value,0,Max*sizeof(Point));
		memset(HashConn,0,sizeof(int)*Max*Max);
		
		for(i=1;i<=n;i++)
		{
			cin>>x>>y;
			Value[i].x = x;
			Value[i].y = y;
			SetLeft[i] = i;
		}
		
		for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
Map[i][j] = GetDisDB(Value[i].x,Value[i].y,Value[j].x,Value[j].y);
		Map[j][i] = Map[i][j];
		}


		cin>>p;

		for(i=1;i<=p;i++)
		{
			cin>>a>>b;
			SetZero(a,b);
			HashConn[a][b] = 1;
			HashConn[b][a] = 1;
		}
		
		ConnEndIndex = 0;	
		LeftEndIndex = n;
		RemoveIndexFromLeft(1);
		AddIndexToSetConn(1);
		Build(n);

	}

	return 0;
}

• 两行的东西都写成函数？调用起来浪费多少时间（pascal的习惯真是……） (2211) frkstyc 2005-07-14 13:02:40
  • Re:两行的东西都写成函数？调用起来浪费多少时间（pascal的习惯真是……） (15) springtty 2005-07-14 13:20:24
    • 你的Prim写坏了, 应该是O(n^2)的，你写成了O(n^3) (19) xfxyjwf 2005-07-14 13:43:49
      • 没写坏，这个是最原始的prim (0) frkstyc 2005-07-14 13:45:15
        • 也太原始了．．． (0) xfxyjwf 2005-07-14 13:48:20
          • 不原始的话他就过了 (0) frkstyc 2005-07-14 13:50:50
    • Re:两行的东西都写成函数？调用起来浪费多少时间（pascal的习惯真是……） (19) 20092378 2010-07-18 19:51:05
• prim (1560) 00448242 2005-07-14 14:04:06
  • Re:prim (1882) springtty 2005-07-14 14:15:02