poj3164

/*
분석:
    최소 트 리 템 플 릿 문제.
    이것 괜찮아요?http://www.zlinkin.com/?p=63
                                 2013-04-26
*/
#include"iostream"
#include"cstdio"
#include"cmath"
#include"cstring"
using namespace std;
const int N=111;
const int inf=INT_MAX;

int n,m,root,x[N],y[N];
double dis[N][N],ans;
int pre[N],inc[N],vis[N];			//incircle

int min(int a,int b){
	return a>b?b:a;
}
void build_map()
{
	int i,l;
	int a,b;
	for(i=1;i<=n;i++)	scanf("%d%d",&x[i],&y[i]);
	for(i=1;i<=n;i++)
	for(l=1;l<=n;l++)
		dis[i][l]=inf;
	while(m--)
	{
		scanf("%d%d",&a,&b);
		dis[a][b]=sqrt(1.0*(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
	}
}
void dfs(int k)
{
	vis[k]=1;
	for(int i=1;i<=n;i++)
	{
		if(dis[k][i]==inf)	continue;
		if(vis[i])	continue;
		dfs(i);
	}
}
int Judge()
{
	for(int i=1;i<=n;i++)	if(!vis[i])	return 1;
	return 0;
}

int find_c()
{
	int i,l,j;
	pre[root]=root;
	//   node
	for(i=1;i<=n;i++)
	{
		if(i==root)	continue;
		if(inc[i])	continue;
		pre[i]=i;
		dis[i][i]=inf;
		for(l=1;l<=n;l++)
		{
			if(inc[l])	continue;
			if(dis[pre[i]][i]<=dis[l][i])	continue;
			pre[i]=l;
		}
	}
	//  
	for(i=1;i<=n;i++)
	{
		if(inc[i])	continue;
		memset(vis,0,sizeof(vis));
		j=i;
		while(!vis[j])
		{
			vis[j]=1;
			j=pre[j];
		}
		if(j==root)	continue;
		return j;
	}
	return -1;
}

void update(int k)
{
	int i,j;
	ans+=dis[pre[k]][k];
	//ans
	for(j=pre[k];j!=k;j=pre[j])
	{
		inc[j]=1;		//    
		ans+=dis[pre[j]][j];
	}
	//          
	for(i=1;i<=n;i++)
	{
		if(inc[i])	continue;
		if(dis[i][k]==inf)	continue;
		dis[i][k]-=dis[pre[k]][k];
	}
	//   
	for(j=pre[k];j!=k;j=pre[j])
	{
		for(i=1;i<=n;i++)
		{
			if(inc[i])	continue;
			if(dis[i][j]==inf)	continue;
			dis[i][k]=min(dis[i][k],dis[i][j]-dis[pre[j]][j]);
			dis[k][i]=min(dis[k][i],dis[j][i]);
		}
	}
}
void solve()
{
	int i,t;
	ans=0;
	memset(inc,0,sizeof(inc));
	while((t=find_c())!=-1)	update(t);
	for(i=1;i<=n;i++)
	{
		if(i==root)	continue;
		if(inc[i])	continue;		//     root,    root   1 ,     i 2   
		ans+=dis[pre[i]][i];
	}
	printf("%.2lf
",ans); } int main() { while(scanf("%d%d",&n,&m)!=-1) { root=1; build_map(); memset(vis,0,sizeof(vis)); dfs(1); if(Judge()) {printf("poor snoopy
");continue;} solve(); } return 0; }

좋은 웹페이지 즐겨찾기