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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1944Fiber Communications题解  

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

  下载LOFTER 我的照片书  |
                                                                光纤通信
                                                        BY   LGS
题目大意:给你N个点的环,和M对关系:A,B表示A和B之间需要相互通信,而你需要连边,但只能连相邻的边,求满足M对关系的同时,最小的连边数量为多少。

题解:此题难度较大,至少一开始我不会。参考了网上的题解才发现,其实一开始我考虑的:A,B相连,那是正着连还是背着连,这样要枚举每个点,所以只能搜索2^1000吓死了。但后来才恍然大悟,如果我们枚举N条边,这样是不是可以代替以上枚举呢。哈哈,这样是可以的。因为这个环中一定存在断开的边,若你全连N条边,那么任意两条边都可以到达了,而且不会有这种情况(题目里是或说了)。这样只要枚举一条断开的边即可,相信大家都会做了吧,即变成了链。

总结:模拟+枚举,思维复杂度较高。
代码:#include<cstdio>
#include<cstring>
using namespace std;
int i,j,n,m,p,ans,c;
int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a<b)?a:b;}
int f[1001],x[10001],y[10001];
int main()
{
 scanf("%d%d",&n,&m);ans=999999999;
 for (i=1;i<=m;i++)
  {scanf("%d%d",&x[i],&y[i]);
  if (x[i]>y[i]){c=x[i];x[i]=y[i];y[i]=c;}
  }
for (i=1;i<=n;i++)
 {
 memset(f,0,sizeof(f));
  for (j=1;j<=m;j++)
      {
      if (i+1<=x[j]||i>=y[j])
       f[x[j]]=max(f[x[j]],y[j]);
       else {
            f[1]=max(f[1],x[j]);
            f[y[j]]=n+1;
            }
      }
  int t=0;int sum=0;
  for (j=1;j<=n;j++)
      {
      if (f[j]>t)
          {
          sum+=f[j]-max(j,t);
          t=f[j];
          }
      }
 ans=min(sum,ans);
 }
printf("%d",ans);
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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