> 用了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;
> }

• 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