Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Prim算法,我把输入的数据看成了森林,先对数据进行一遍松弛,再进行常规的Prim,求解为什么会wrong

Posted by lzh0108 at 2017-03-11 10:37:33 on Problem 3625
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator