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

我用的朱刘算法不知哪里错了,求教各位大神

Posted by zhangshuheng at 2012-09-17 20:39:36 on Problem 3164
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define maxn 105
#define INF 2000000000
double arr[maxn][maxn];
int n,m;
int st,ed;
struct node
{
    double x;
    double y;
}brr[105];
double zhuliu()
{
    bool visited[maxn];
    bool flag[maxn];
    int pre[maxn];
    double sum=0;
    int i,j,k;
    for(i=0;i<n;i++)
    {
        flag[i]=false;
        arr[i][i]=INF;
    }
    pre[0]=0;
    while(true)
    {
        for(i=1;i<n;i++)
        {
            if(flag[i])
            continue;
            pre[i]=i;
            for(j=0;j<n;j++)
            if(!flag[j]&&arr[j][i]<arr[pre[i]][i])
            pre[i]=j;
            if(pre[i]==i)
            return -1;
        }
        for(i=1;i<n;i++)
        {
            if(flag[i])
            continue;
            for(j=0;j<n;j++)
            visited[j]=false;
            visited[0]=true;
            j=i;
            do
            {
                visited[j]=true;
                j=pre[j];
            }while(!visited[j]);
            if(!j)
            continue;
            i=j;
            do
            {
                sum+=arr[pre[j]][j];
                j=pre[j];
            }while(j!=i);
            j=i;
            do
            {
                for(k=0;k<n;k++)
                if(!flag[k]&&arr[k][j]<INF&&k!=pre[j])
                arr[k][j]-=arr[pre[j]][i];
                j=pre[j];
            }while(j!=i);
            for(j=0;j<n;j++)
            {
                if(j==i)
                continue;
                for(k=pre[i];k!=i;k=pre[k])
                {
                    if(arr[k][j]<arr[i][j])
                    arr[i][j]=arr[k][j];
                    if(arr[j][k]<arr[j][i])
                    arr[j][i]=arr[j][k];
                }
            }
            for(j=pre[i];j!=i;j=pre[j])
            flag[j]=true;
            break;
        }
        if(i==n)
        {
            for(i=1;i<n;i++)
            if(!flag[i])
            sum+=arr[pre[i]][i];
            break;
        }
    }
  return sum;
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            arr[i][j]=INF;
        for(int i=0;i<n;i++)
        scanf("%lf %lf",&brr[i].x,&brr[i].y);
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&st,&ed);
            st--;
            ed--;
            arr[st][ed]=sqrt((brr[st].x-brr[ed].x)*(brr[st].x-brr[ed].x)+(brr[st].y-brr[ed].y)*(brr[st].x-brr[ed].x));
        }
        double ans=zhuliu();
        if(ans==-1)
        printf("poor snoopy\n");
        else
        printf("%.2lf\n",ans);
    }
    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