| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1109 人关注过本帖
标题:请教一下为什会超时(限时 15s)(我用了16秒)(最大流,对偶图)
只看楼主 加入收藏
xuzc
Rank: 1
等 级:新手上路
帖 子:15
专家分:9
注 册:2016-9-13
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:9 
请教一下为什会超时(限时 15s)(我用了16秒)(最大流,对偶图)
//题目链接   http://www.
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int cnt,i,j,x,xx,xxx,h,t,s,hh[7010000],n,m,w;
bool dd[2010000];
int e,l[2010000],d[2010000];
struct node{
 int v,next,z;
}b[6510000];
inline void add(int aa,int bb,int cc)
{
 b[++cnt].v=bb;
 b[cnt].next=hh[aa];
 b[cnt].z=cc;
 hh[aa]=cnt;
 b[++cnt].v=aa;
 b[cnt].next=hh[bb];
 b[cnt].z=cc;
 hh[bb]=cnt;
}
void add1()
{
 for(i=1;i<m;++i)
 {
  scanf("%d",&x);
  add(i*2,t,x);
  }
 for(i=2;i<n;++i)
 {
  for(j=1;j<m;++j)
  {
   scanf("%d",&x);
   add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-m*2+1,x);
  }
 }
 for(j=1;j<m;++j)
 {
  scanf("%d",&x);
  add(s,(n-2)*2*(m-1)+j*2-1,x);
 }   
}
void add2()
{
 for(i=1;i<n;++i)
 {
  scanf("%d",&x);xx=(i-1)*(m-1)*2+1;
  add(s,xx,x);
  for(j=2;j<m;++j)
  {
      scanf("%d",&x);xx+=2;
      add(xx-1,xx,x);
   }
  scanf("%d",&x);
  add(xx+1,t,x);
 }   
}
inline void add3()
{
 
 for(i=1;i<n;++i)
 {
  for(j=1;j<m;++j)
  {
   scanf("%d",&x);
   add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-1,x);
  }
 }   
}
void spfa()
{
 dd[s]=true;
 h=0;w=0;
 memset(l,0x3f,sizeof(l));
 l[s]=0;
 while(1)
 {
  if(h>w)break;
  for(i=hh[s];i;i=b[i].next)
  {
   e=b[i].v;
   if(l[s]+b[i].z<l[e]){
       l[e]=l[s]+b[i].z;
       if(!dd[e])d[++w]=e,dd[e]=true;
   }   
  }
  dd[s]=false;
  s=d[++h];
 }
}
int main()
{
 scanf("%d %d",&n,&m);
 if(n==m&&n==1){
  printf("0");
  return 0;
 }
 s=0;
 t=2*(n-1)*(m-1)+1;
 add1();
 add2();
 add3();
 spfa();
 printf("%d",l[t]);
 return 0;
}
搜索更多相关主题的帖子: include 
2016-09-17 19:29
xuzc
Rank: 1
等 级:新手上路
帖 子:15
专家分:9
注 册:2016-9-13
收藏
得分:0 
求讲解一下在哪超时,缩短时间该怎么写,O(∩_∩)O谢谢
2016-09-17 19:32
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1745
专家分:3216
注 册:2015-12-2
收藏
得分:0 
这个算法我不懂,我只想问你为什么要用命名空间,命名空间是c++的内容。这样不影响执行时间吗?
2016-09-17 19:59
张子木
Rank: 2
等 级:论坛游民
帖 子:2
专家分:20
注 册:2016-9-14
收藏
得分:0 
看不懂
2016-09-17 21:02
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:6 
这道题用通俗的方法来说就是“用最小代价 破坏连通图

然后我拿着这个关键词百度了一下,其中有一个博客  http://blog.  人家的题目还稍微复杂点他要实现的是使多个目标结点不得联通的前提下留下“最大生成树”

他的代码比你短很多。从他的分析里面我得知:
用Kruskal算法求最大生成树,用并查集来维护两个导弹不能在一个连通图中
这道题是有现成的算法能实现的。所以我建议楼主查阅一下Kruskal算法的前世今生,我相信你就知道自己为什么会超时了。


因为还要照顾那些非C语言的用户,OJ平台上限定的时间通常都是两三倍于正常运行时间。我建议你不要纠结于那一秒。推翻重写。


---------------------------------------------------
补充:刚百度了一下“最大流 对偶图”的概念。然后我发现自己完全没能力理解。。所以我估计自己把这道“狼抓兔子”的问题归类归错了。。。所以前面这些仅供参考,错了轻拍


[此贴子已经被作者于2016-9-18 00:03编辑过]


φ(゜▽゜*)♪
2016-09-17 23:52
ehszt
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:40
帖 子:1745
专家分:3216
注 册:2015-12-2
收藏
得分:1 
不得不承认,算法也是一门学问啊!
2016-09-18 08:15
xuzc
Rank: 1
等 级:新手上路
帖 子:15
专家分:9
注 册:2016-9-13
收藏
得分:0 
回复 3楼 ehszt
不影响啊
2016-09-19 21:56
xuzc
Rank: 1
等 级:新手上路
帖 子:15
专家分:9
注 册:2016-9-13
收藏
得分:0 
回复 5楼 书生牛犊
我跟另一个人代码差不多,但是人家只用了三秒多,我想知道在哪多了十几秒
http://
2016-09-19 21:59
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:0 
回复 8楼 xuzc
这玩意我不懂。既然你觉得你和人家代码差不多那就逐行对比就行了。

我连对偶图最大流都搞不定,更加知不得后面的优化怎么回事。

φ(゜▽゜*)♪
2016-09-19 22:07
linlulu001
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:20
帖 子:944
专家分:4047
注 册:2016-4-13
收藏
得分:13 
那个链接,看了下。
除了void spfa()这个函数之外,从时间复杂度上看,其它函数的差别在运算时间上影响不大
要不楼主你用时间代码来计算下void spfa()里的while(1)从循环开始到结束要用多少时间,看看结果如何。
2016-09-19 23:12
快速回复:请教一下为什会超时(限时 15s)(我用了16秒)(最大流,对偶图)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022912 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved