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