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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1258Agri-Net题解  

2014-03-09 18:07:11|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                            电缆连接
                                                            BY  LGS
题目大意:给你N个点,并告知了每个点之间的边的权值,求连接这N个点的最小代价。

题解:此题是赤裸裸的最小生成树。最小生成树有两种,克鲁斯卡尔和prime算法。此题点为1000个,用prime的N^2算法较为简单。用克鲁斯卡尔:边数为N*(N-1)/2,记为N^2,则算法为O(n^2logN),也可以过掉。

总结:水题一道。注意读入的多组数据。

代码:
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,ans,n,k;
int a[200][200],dis[200];
bool b[200];
int main()
{
while (scanf("%d",&n)!=EOF){
 for (i=1;i<=n;i++)
 for (j=1;j<=n;j++)
  scanf("%d",&a[i][j]);
memset(dis,60,sizeof(dis));
memset(b,false,sizeof(b));
dis[1]=0;ans=0;
while (1)
      {
      int min=999999999;int flag=0;
      for (j=1;j<=n;j++)
            {
            if ((min>dis[j])&&(!b[j]))
                    {
                    min=dis[j];
                    flag=j;
                    }
            }
      if (flag==0) break;
      b[flag]=true;ans+=min;
      for (j=1;j<=n;j++)
            if (dis[j]>a[flag][j])
                 {
                 dis[j]=a[flag][j];
                 }
      } 
printf("%d\n",ans); 
                  }
return 0;
}



  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018