548
技術社區[雲棲]
poj 1751 Highways MST
水到家的一道題，居然WA了3次……沒注意到距離是double……沒有輸出的話要輸出一行空行
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1E9
using namespace std;
double d[751];
double dis[751][751];
bool vis[751];
int near[751];
struct node
{
int x,y;
};
node org[751];
int n;
int prim()
{
double Min,ans=0;
int K=n,i,t,now=0;
while(K--)
{
Min=INF;
for(i=0;i<n;i++)
if(!vis[i]&&d[i]<Min)
Min=d[i],now=i;
vis[now]=1;
if(now)
{
ans+=Min;
if(Min)printf("%d %d\n",now+1,near[now]+1);
}
for(i=0;i<n;i++)
{
if(vis[i]||d[i]<=dis[now][i])continue;
d[i]=dis[now][i];near[i]=now;
}
}
return ans;
}
int main()
{
int i,j,m,a,b,T=0;
while(~scanf("%d",&n))
{
memset(vis,0,sizeof(vis));
memset(d,127,sizeof(d));
for(i=0;i<n;i++)
scanf("%d%d",&org[i].x,&org[i].y);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
dis[j][i]=dis[i][j]=sqrt((org[i].x-org[j].x)*(org[i].x-org[j].x)+(org[i].y-org[j].y)*(org[i].y-org[j].y));
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
dis[a-1][b-1]=dis[b-1][a-1]=0;
}
if(!prim())puts("");
}
}
最後更新：2017-04-04 07:03:45