2009-3-4pku3164.txt

MDSD算法！ 这个是我们中国人自己发现的一个算法！ 在ACM中属于比较难得题目！ 我只有有一个模板

#include<stdio.h>
#include<string.h>
#include<math.h>
const int MAX=105;
const double INF=1e200;
typedef struct Point 
{
	double x;
	double y;
}Point;
Point p[MAX];
//以下两个函数为MDST算法的模板！
int n,used[MAX],pass[MAX],eg[MAX],more,queue[MAX];
double g[MAX][MAX];//如果是整数将double改为int
void combine(int id,double &sum)
{
	int tot=0,from,i,j,k;
	for(;id!=0&&!pass[id];id=eg[id])
	{queue[tot++]=id;pass[id]=1;}
	for(from=0;from<tot&&queue[from]!=id;from++);
	if(from==tot)return;more=1;
	for(i=from;i<tot;i++)
	{
		sum+=g[eg[queue[i]]][queue[i]];
		if(i!=from)
		{ 
			used[queue[i]]=1;
		    for(j=1;j<=n;j++)
				if(!used[j])
			       if(g[queue[i]][j]<g[id][j])
					   g[id][j]=g[queue[i]][j];
		}
	}
	for(i=1;i<=n;i++)
		if(!used[i]&&i!=id)
		{
		  for(j=from;j<tot;j++)
		  {
			  k=queue[j];
		    if(g[i][id]>g[i][k]-g[eg[k]][k])
			   g[i][id]=g[i][k]-g[eg[k]][k];
		  }
		}
}
double  MDST(int root)//return the total length of MDST
{
	int i,j,k;
	double sum=0;//如果是整数将double改为int
	memset(used,0,sizeof(used));
	for(more=1;more;)
	{
	    more=0;
	    memset(eg,0,sizeof(eg));
	    for(i=1;i<=n;i++) 
			if(!used[i]&&i!=root)
			{
		      for(j=1,k=0;j<=n;j++) 
				  if(!used[j]&&i!=j)
			         if(k==0||g[j][i]<g[k][i])
						 k=j;
	            eg[i]=k;
			}
	memset(pass,0,sizeof(pass));
	for(i=1;i<=n;i++)
		if(!used[i]&&!pass[i]&&i!=root)
			combine(i,sum);
	}
	for(i=1;i<=n;i++)
		if(!used[i]&&i!=root)
			sum+=g[eg[i]][i];
	return sum;
}
double Dis(Point a,Point b)
{
	double dis;
	dis=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
	return sqrt(dis);
}
int main()
{
	int i,m,st,ed;
	double ans;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		for(i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=INF;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&st,&ed);
			g[st][ed]=Dis(p[st],p[ed]);
		}
		ans=MDST(1);
		if(ans<INF)
		   printf("%.2lf\n",ans);
		else
			printf("poor snoopy\n");
	}
	return 0;
}
/*
4 6
0 6
4 6
0 0
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3


31.19
poor snoopy
*/