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   知识库   博问   管理


<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜