| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Prim算法,我把输入的数据看成了森林,先对数据进行一遍松弛,再进行常规的Prim,求解为什么会wrong#include<stdio.h>
#include<math.h>
#include<string.h>
#define maxn 1000+10
#define min(a,b) (a<b?a:b)
const double inf=0x3f3f3f3f;
double e[maxn][maxn],d[maxn];
bool vis[maxn];
int x[maxn],y[maxn];
int n,m;
void Prim()
{
int i,j,v;
for(i=1; i<=n; i++)
{
if(vis[i])
{
for(j=1; j<=n; j++)//松弛
if(d[j]>e[i][j])
d[j]=e[i][j];
}
}
// for(int i=1;i<=n;i++)
// d[i]=e[1][i];
// vis[1]=1;
double sum=0,minn;
while(1)
{
minn=inf;
for(i=1; i<=n; i++)
if(!vis[i]&&d[i]<minn)
minn=d[i],v=i;
if(minn==inf)
break;
vis[v]=true,sum+=minn;
for(i=1; i<=n; i++)
if(!vis[i]&&d[i]>e[v][i])
d[i]=e[v][i];
}
printf("%.2lf\n",sum);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
e[i][j]=e[j][i]=(i==j?0:inf);
d[i]=inf,vis[i]=0;
}
double w;
for(int i=1; i<=n; i++)
{
scanf("%d%d",&x[i],&y[i]);
for(int j=1; j<i; j++)
{
w=sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
e[i][j]=e[j][i]=w;
}
}
int u,v;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&u,&v);
vis[u]=vis[v]=true;
e[u][v]=e[v][u]=0;
}
Prim();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator