toj 最小生成树集萃

1924 jungle road
#include<iostream>
#include
<cstring>
using namespace std;
 
int path[30][30];
int cost[30];
int flag[30];

int prim(int n)
{
    
int sum=0;
    
int i,j,min,v;
    v
=0;
    flag[v]
=1;
    
for(i=0;i<n-1;i++)
    
{
        
for(j=0;j<n;j++)
        
if(!flag[j]&&path[v][j]<cost[j])
        cost[j]
=path[v][j];
        min
=1<<30;
        
for(j=0;j<n;j++)
        
if(!flag[j]&&cost[j]<min)
        
{
            min
=cost[j];
            v
=j;
        }

        flag[v]
=1;
        sum
+=min;
    }

    
return sum ;
}

int main()
{
    
int n,i,j,v,min,m,c;
    
char ch;
    
while(scanf("%d",&n)!=EOF&&n)
    
{
          memset(path,
0x1f,sizeof(path));
          memset(cost,
0x1f,sizeof(cost));
          memset(flag,
0,sizeof(flag));
          
for(i=0;i<n;i++)
          path[i][i]
=0;
          
for(i=0;i<n-1;i++)
          
{
              getchar();
              scanf(
"%c",&ch);
              scanf(
"%d",&m);
              
for(j=0;j<m;j++)
              
{
                     getchar();
                     scanf(
"%c",&ch);
                     scanf(
"%d",&c);
                     path[i][ch
-'A']=path[ch-'A'][i]=c;
              }

          }

          printf(
"%d\n",prim(n));
    }

    
return 0;
}
1348 freckles
#include<iostream>
#include
<iomanip>
#include
<cmath>
using namespace std;

int x[501];
int y[501];

struct node
{
       
int s,e;
       
int d;
       
bool operator<(const node& a)const
       
{
            
return d<a.d;
       }

}
edges[130000];
int father[505];
int n,m;
int find(int i)
{
    
if(father[i]==i)
    
return i;
    
else
    
return father[i]=find(father[i]);
}

void unin(int i,int j)
{
    
int a=find(i);
    
int b=find(j);
    father[a]
=b;
}


int f(int k)
{
     
int i,j;
     j
=0;
     
for(i=0;i<k&&j<m-n;i++)
     
if(find(father[edges[i].s])!=find(father[edges[i].e]))
     
{
        unin(edges[i].s,edges[i].e);
        j
++;
        
if(j==m-n)
        
return edges[i].d;
     }

}


int main()
{
    
int i,j,k,cas_num;
    scanf(
"%d",&cas_num);
    
while(cas_num--)
    
{
           scanf(
"%d%d",&n,&m);
           
for(i=0;i<m;i++)
           father[i]
=i;
           k
=0;
           
for(i=0;i<m;i++)
           
{
                  cin
>>x[i]>>y[i];
                  
for(j=0;j<i;j++)
                  
{
                      edges[k].s
=j;
                      edges[k].e
=i;
                      edges[k].d
=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);
                      k
++;
                  }

           }

           sort(edges,edges
+k);
           cout
<<fixed<<setprecision(2)<<sqrt(f(k)*1.0)<<endl;
    }

    
return 0;
}
 

1830.   Tangled in Cables

#include<iostream>
#include
<map>
#include
<algorithm>
#include
<string>
using namespace std;
struct node
{
       
int s,e;
       
double d;
       
bool operator<(const node& a)const
       
{
            
return d<a.d;
       }

}
edges[60000];
int father[505];
int find(int i)
{
    
if(father[i]==i)
    
return i;
    
else
    
return father[i]=find(father[i]);
}

void unin(int i,int j)
{
    
int a=find(i);
    
int b=find(j);
    father[a]
=b;
}


void f(double total,int n,int m)
{
     
int i,j;
     
double sum=0;
     j
=0;
     
for(i=0;i<m&&j<n-1&&sum<total;i++)
     
if(find(father[edges[i].s])!=find(father[edges[i].e]))
     
{
        unin(edges[i].s,edges[i].e);
        sum
+=edges[i].d;
        j
++;
     }

     
if(j==n-1)
     printf(
"Need %.1lf miles of cable\n",sum);
     
else
     printf(
"Not enough cable\n");
}

     
int main()
{
    map
<string,int>mm;
    
int i,n,m;
    
double cost,total;
    
double ans;
    
string s1,s2;
    
char ch1[21],ch2[21];
    
while(cin>>total)
    
{
          scanf(
"%d",&n);
          
for(i=0;i<n;i++)
          father[i]
=i;
          
for(i=0;i<n;i++)
          
{
              scanf(
"%s",ch1);
              s1
=ch1;
              mm[s1]
=i;
          }

          scanf(
"%d",&m);
          
for(i=0;i<m;i++)
          
{
               scanf(
"%s %s",ch1,ch2);
               scanf(
"%lf",&cost);
               s1
=ch1;
               s2
=ch2;
               edges[i].s
=mm[s1];
               edges[i].e
=mm[s2];
               edges[i].d
=cost;
          }

          sort(edges,edges
+m);
          f(total,n,m);
    }
          
    
return 0;
}

2288.   Highways

#include<iostream>
#include
<algorithm>
using namespace std;

int x[760],y[760];
int father[760];
int find(int i)
{
    
if(father[i]==i)
    
return i;
    
else
    
return father[i]=find(father[i]);
}

void unin(int i,int j)
{
     
int a=find(i);
     
int b=find(j);
     father[a]
=b;
}

struct node
{
       
int s,e;
       
int d;
       
bool operator <(const node& a)const
       
{
            
if(d!=a.d)
            
return d<a.d;
            
else 
            
return s<a.s;
       }

}
edges[300000];
void kruscal(int n,int k)
{
     
int j=0;
     
for(int i=0;i<k&&j<n-1;i++)
     
if(find(edges[i].s)!=find(edges[i].e))
     
{
        unin(edges[i].s,edges[i].e);
        printf(
"%d %d\n",edges[i].s,edges[i].e);
        j
++;
     }

}


int main()
{
    
int n,m,i,j,k,a,b;
    
while(scanf("%d",&n)!=EOF)
    
{
        
for(i=0;i<=n;i++)
        father[i]
=i;
        k
=0;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d%d",&x[i],&y[i]);
            
for(j=1;j<i;j++)
            
{
                edges[k].s
=j;
                edges[k].e
=i;
                edges[k].d
=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);
                k
++;
            }

        }

        sort(edges,edges
+k);
        scanf(
"%d",&m);
        
for(i=0;i<m;i++)
        
{
         scanf(
"%d%d",&a,&b);
         unin(a,b);
         }

         kruscal(n,k);
    }

    
return 0;
}

TOJ 2172
#include<iostream>
#include
<map>
#include
<algorithm>
#include
<string>
using namespace std;
struct node
{
       
int s,e;
       
int d;
       
bool operator<(const node& a)const
       
{
            
return d<a.d;
       }

}
edges[60000];
int father[5005];
int n,t;
int find(int i)
{
    
if(father[i]==i)
    
return i;
    
else
    
return father[i]=find(father[i]);
}

void unin(int i,int j)
{
    
int a=find(i);
    
int b=find(j);
    father[a]
=b;
}


int f(int k,int n)
{
     
int i,j,sum;
     j
=sum=0;
     
for(i=0;i<k&&j<n-1;i++)
     
if(find(father[edges[i].s])!=find(father[edges[i].e]))
     
{
        unin(edges[i].s,edges[i].e);
        sum
+=edges[i].d;
        j
++;
     }

     
return sum;
}

     
int main()
{
    map
<string,int>m;
    
int i,j,cost,k;
    
int ans;
    
string s1,s2;
    
char ch1[11],ch2[11];
    
while(scanf("%d%d",&n,&t)!=EOF)
    
{
          
          j
=0;
          k
=t;
          
for(i=0;i<=n;i++)
          father[i]
=i;
          
for(i=0;i<t;i++)
          
{
              getchar();
              scanf(
"%s %s",&ch1,&ch2);
              scanf(
"%d",&cost);
              s1
=ch1;
              s2
=ch2;
              map
<string,int>::iterator it;
              it
=m.find(s1);
              
if(it==m.end())
              
{
                 m[s1]
=j;
                 edges[k].s
=0;
                 edges[k].e
=j++;
                 edges[k].d
=10;
                 k
++;
              }
 
              it
=m.find(s2);
              
if(it==m.end())
              
{
                 m[s2]
=j;
                 edges[k].s
=0;
                 edges[k].e
=j++;
                 edges[k].d
=10;
                 k
++;
              }
 
              edges[i].s
=m[s1];
              edges[i].e
=m[s2];
              edges[i].d
=cost;
          }

          ans
=(n-j+1)*10;
          sort(edges,edges
+k);
          ans
+=f(k,j);
          printf(
"The total cost is %d Yuan %d Jiao.\n",ans/10,ans%10);
    }

    
return 0;
}

          

posted on 2010-05-13 12:00 YUANZX 阅读(282) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年2月>
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜