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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2139Six Degrees of Cowvin Bacon题解  

2014-03-21 20:42:48|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                    六度培根 
                                              BY   LGS
题目大意:给你N个奶牛,然后M对关系,每一行表示这些K个奶牛在做同一个电影。如果他们在做同一个电影那么他们的度即距离为1,如果他们被间接的连接,那么他们的度为间接的距离和。

题解:明显是folyed,水题一道不解释。
总结:水题要求一遍A
代码:
#include<cstdio>
#include<cstring>
#define maxn 305
using namespace std;
double ans,max;
int i,j,k,n,m,x,a[maxn],f[maxn][maxn];
int min(int a,int b){return (a>b)?b:a;}
int main()
{
 scanf("%d%d",&n,&m);
 memset(f,0x3f,sizeof(f));
 for (i=1;i<=m;i++)
  {
  scanf("%d",&x);
  for (j=1;j<=x;j++) scanf("%d",&a[j]);
  for (j=1;j<=x-1;j++)
   for (k=j+1;k<=x;k++) {f[a[j]][a[k]]=1;f[a[k]][a[j]]=1;}
  }
for (k=1;k<=n;k++)
 for (i=1;i<=n;i++)if (i!=k)
  for (j=1;j<=n;j++) if ((j!=k)&&(j!=i))
                f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
 max=999999999;
for (i=1;i<=n;i++){
                  ans=0;
 for (j=1;j<=n;j++)if (i!=j)
               ans+=f[i][j];
                  ans=(double)(ans/(n-1));
               if (ans<max)max=ans;
                  }
printf("%d\n",(int)(max*100));
return 0;
}
  评论这张
 
阅读(549)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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