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过了,Krustra就WA 5555~~~~

Posted by JerryFang at 2013-04-29 15:46:39 on Problem 2031
通过本次实验,我掌握了MST算法。
K版本:(WA)怎么回事?
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;

#define MAXN 110
float x[MAXN],y[MAXN],z[MAXN],r[MAXN];
float dd[MAXN*MAXN];
int p[MAXN*MAXN];
    
int cmp(const int x,const int y){return dd[x]<dd[y];}
int find(int x)
{
    if(x == p[x])
       return x;
    return find(p[x]);
}

int main()
{
    int num=0;
    int edge=0;
    int v[MAXN*MAXN];
    int u[MAXN*MAXN];
    int rr[MAXN*MAXN];
    float total = 0;
    
    while(scanf("%d",&num)!=EOF)
    {
        if(!num)
            break;
            
        edge = 0;
        total = 0;
        memset(dd,0,sizeof(dd));
        
        for(int i=0;i<num;i++)
            scanf("%f %f %f %f",&x[i],&y[i],&z[i],&r[i]);
            
        for(int i=0;i<num;i++)
        for(int j=i+1;j<num;j++)
        {

           dd[edge] = (float)(sqrt( pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2)) - r[i] -r[j]);
           u[edge] = i;
           v[edge] = j;

           if(dd[edge]<0)
               dd[edge] = (float)0;

           edge++;
        }       

        for(int i=0;i<edge;i++)
            rr[i] = i;
        
        sort(rr,rr+edge,cmp);
        
        for(int i=0;i<edge;i++)
            p[i] = i;
            
        for(int i=0;i<edge;i++)  
        {
            int bian=rr[i];
            int uroot = find(u[bian]);
            int vroot = find(v[bian]);
            if(uroot != vroot)
            {
                     
            total+=dd[bian];
            p[uroot]=vroot;
            
            }
                    
        }     
       printf("%0.3lf\n",total);             
    }
    return 0;
}

P:AC了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
using namespace std;
#define MAXN 110

int main()
{
    int num;
    float dd[MAXN][MAXN];
    float d[MAXN];
    bool flag[MAXN];
    float x[MAXN],y[MAXN],z[MAXN],r[MAXN];
    float total=0;

    while(scanf("%d",&num)!=EOF)
    {
       if(!num)
       break;
    
       memset(flag,false,sizeof(flag));
       for(int i=0;i<num;i++)
           d[i]=10000;
       total =0 ;
    
       for(int i=0;i<num;i++)
           scanf("%f %f %f %f",&x[i],&y[i],&z[i],&r[i]);
                
       for(int i=0;i<num;i++)
       for(int j=0;j<num;j++)
        {

           dd[i][j] = (float)(sqrt( pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2)) - r[i] -r[j]);
           if(dd[i][j]<0)
               dd[i][j] = (float)0; 
               //cout<<dd[i][j]<<endl;
        }        
         
        d[0] = 0;
        
        for(int i=0;i<num;i++)
        {
                double min = 10000;
                int mark;
                
                for(int j=0;j<num;j++)
                {
                    if(!flag[j] && d[j]<=min)
                    {
                       min = d[j];
                       mark = j;
                    }
                }   
                

                flag[mark] = true;     
                total+=d[mark];

                for(int j=0;j<num;j++)
                {
                    if(!flag[j] && dd[mark][j] < d[j])
                       d[j] = dd[mark][j];        
                }
        }                      
        printf("%0.3lf\n",total);
    }
    return 0;
}

/************
3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
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