> #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;
> }

• O(n^3)的Prim,过不了 (0) xfxyjwf 2005-07-14 19:11:58