#include<stdio.h>
#include "math.h"

typedef struct Graph{
	double ArrayGraph[760][760];
    int Vnum;
}Graph;

typedef struct CTree{
	int  TVex[760],Tnum;
	int  LVex[760],Lnum;
}CTree;

typedef struct MinVex{
	int  i;
	double  Weight;
}MinVex;

Graph CurGraph;
CTree CurTree;

double distance(int x1,int y1,int x2,int y2 )
{

	return 	(pow((x1-x2),2)+pow((y1-y2),2));

}

void InsertCTree(int Vnum);
int FindMin(double *MinWeight);

int main()
{
	int i,j,Qnum,Vnum,Xnum,a[750][2],b[750][2];
    double MinWeight=0;


    CurTree.Lnum=0;  CurTree.Tnum=0;
	scanf("%d",&CurGraph.Vnum);
	for(i=0;i<CurGraph.Vnum;i++){
		scanf("%d%d",&a[i][0],&a[i][1]);
          CurTree.LVex[i]=i;
		  CurTree.Lnum++;
		  }
    
	for(i=0;i<CurGraph.Vnum;i++)
		for(j=i+1;j<CurGraph.Vnum;j++)
			CurGraph.ArrayGraph[i][j]=distance(a[i][0],a[i][1],a[j][0],a[j][1]);




    scanf("%d",&Qnum);
	for(i=0;i<Qnum;i++){
		scanf("%d%d",&b[i][0],&b[i][1]);
		Vnum=b[i][0];Xnum=b[i][1];
		CurGraph.ArrayGraph[Vnum-1][Xnum-1]=0;
        CurGraph.ArrayGraph[Xnum-1][Vnum-1]=0;
	}

while(CurTree.Lnum!=0){
	i=FindMin(&MinWeight);
	InsertCTree(i);
}
  return 1;
}

void InsertCTree(int Vnum)
{
   int i,j;
  
   for(i=0;i<CurTree.Lnum;i++)
	   if(CurTree.LVex[i]==Vnum)
		   break;
	   
   if(i>=CurTree.Lnum)
	   return;
   
   for(j=i;j<CurTree.Lnum;j++)
	   CurTree.LVex[j]=CurTree.LVex[j+1];
   
   CurTree.Lnum--;

   CurTree.TVex[CurTree.Tnum]=Vnum;
   CurTree.Tnum++;

   return;
}

int FindMin(double *MinWeight)
{
   MinVex CurMinVex;
   int i,j,temp,temp1;

   CurMinVex.Weight=19999;
   if(CurTree.Tnum==0) return 0;
   for(i=0;i<CurTree.Tnum;i++)
	   for(j=0;j<CurTree.Lnum;j++)
		  if(CurTree.TVex[i]>CurTree.LVex[j])
		   {
			   if(CurGraph.ArrayGraph[CurTree.LVex[j]][CurTree.TVex[i]]<CurMinVex.Weight){
                CurMinVex.i=CurTree.LVex[j];
				temp=CurTree.TVex[i];          
				temp1=CurTree.LVex[j];
				CurMinVex.Weight=CurGraph.ArrayGraph[temp1][temp];
			   }
		   }
		   else
		   {if(CurGraph.ArrayGraph[CurTree.TVex[i]][CurTree.LVex[j]]<CurMinVex.Weight){
				CurMinVex.i=CurTree.LVex[j];
				temp=CurTree.TVex[i];          
				temp1=CurTree.LVex[j];
				CurMinVex.Weight=CurGraph.ArrayGraph[temp][temp1];
		   }
		   }
  if((temp<temp1&&CurGraph.ArrayGraph[temp][temp1]!=0)||(temp>temp1&&CurGraph.ArrayGraph[temp1][temp]!=0))
  	      printf("%d %d\n",temp+1,temp1+1);
          return CurMinVex.i;
}

• 总是超时呀 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! (2761) ook 2005-07-14 18:04:37
  • O(n^3)的Prim,过不了 (0) xfxyjwf 2005-07-14 19:11:58