注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2377Bad Cowtractors题解  

2014-03-26 20:10:03|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                 怀牛
                                       BY   LGS
题目大意:有N个点,每个点之间有边,有费用,求连接N个点的最大费用(有点sb).

题解:最大生成树

总结:prime
代码:
  • Source Code
  • #include<cstdio>
    #define maxn 1001
    #define maxx 99999999
    using namespace std;
    int flag,ans,ma,mal,i,j,n,m,k,x,y,c,f[maxn][maxn],dis[maxn];
    int max(int a,int b){return (a>b)?a:b;}
    bool b[maxn];
    int main()
    {
     scanf("%d%d",&n,&m);
     for (i=1;i<=m;i++)
         {
         scanf("%d%d%d",&x,&y,&c);
         f[x][y]=max(f[x][y],c);
         f[y][x]=max(f[x][y],f[y][x]);
         }
    for (i=2;i<=n;i++) dis[i]=-maxx;
    while (1)
        {
       ma=-maxx;mal=0;
       for (j=1;j<=n;j++)
                     if ((dis[j]>ma)&&(!b[j]))
                      {
                      ma=dis[j];mal=j;
                      }
       if (mal==0) break; 
       b[mal]=true;ans+=ma;
       for (j=1;j<=n;j++) if (j!=mal)
                     if (f[mal][j]!=0)
                        dis[j]=max(f[mal][j],dis[j]);
        }
    flag=0;
    for (i=1;i<=n;i++) if (dis[i]==-maxx) {flag=1;break;}
    if (flag==1)
     printf("-1\n");
      else printf("%d\n",ans);
    return 0; 
    } 
                           
  评论这张
 
阅读(0)| 评论(0)