博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[CQOI2014]危桥
阅读量:5827 次
发布时间:2019-06-18

本文共 2073 字,大约阅读时间需要 6 分钟。

题目描述

Alice和Bob居住在一个由N座岛屿组成的国家,岛屿被编号为0到N-1。某些岛屿之间有桥相连,桥上的道路是双

向的,但一次只能供一人通行。其中一些桥由于年久失修成为危桥,最多只能通行两次。Alice希望在岛屿al和a2之间往返an次(从al到a2再从a2到al算一次往返)。同时,Bob希望在岛屿bl和b2之间往返bn次。这个过程中,所有危桥最多通行两次,其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗?

题解

有一个初步的想法,因为图是无向的,所以我们的往返可以看做走两遍。

所以我们就把无向图连出来,然后连上源和汇跑一遍最大流,然后检查是否漫流。

但这样会有一个问题,两股流有可能会有交叉的地方,这样我们有可能会把无解判断成有解。

也就是\(s1->t2\ s2->t1\)

正解非常巧妙,就是把一条路径反过来再跑一遍,如果还漫流,则说明有解。

为什么,这时如果还满流,那么会有\(s1->s2\ t2->t1\)那么这说明\(s1\)是这股流是可以到\(t1\)的,\(s2\)也是可以到\(t2\)的,则它是有解的。

代码

#include
#include
#include
#include
#define N 60#define inf 1e9using namespace std;queue
q;int head[N],tot=1,cur[N],deep[N],n,ans;char s[N][N];inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x;}struct edge{ int n,to,l;}e[N*N*10];inline void add(int u,int v,int l){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l; e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=l;}bool bfs(int s,int t){ memcpy(cur,head,sizeof(head)); memset(deep,0,sizeof(deep)); q.push(s);deep[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(!deep[v]&&e[i].l){ deep[v]=deep[u]+1; q.push(v); } } } return deep[t];}int dfs(int u,int t,int l){ if(u==t||!l)return l; int flow=0,f; for(int &i=cur[u];i;i=e[i].n){ int v=e[i].to; if(deep[v]==deep[u]+1&&(f=dfs(v,t,min(l,e[i].l)))){ e[i].l-=f;e[i^1].l+=f;flow+=f;l-=f; if(!l)break; } } return flow;}int main(){ int a1,a2,an,b1,b2,bn; while(scanf("%d",&n)!=EOF){ a1=rd()+1;a2=rd()+1;an=rd();b1=rd()+1;b2=rd()+1;bn=rd();; for(int i=1;i<=n;++i)scanf("%s",s[i]+1); tot=1; memset(head,0,sizeof(head)); for(int i=1;i<=n;++i) for(int j=1;j

转载于:https://www.cnblogs.com/ZH-comld/p/10562668.html

你可能感兴趣的文章
Nginx 使用 openssl 的自签名证书
查看>>
创业维艰、守成不易
查看>>
PHP环境安装套件:快速安装LAMP环境
查看>>
CSS3
查看>>
ul下的li浮动,如何是ul有li的高度
查看>>
C++ primer plus
查看>>
python mysqlDB
查看>>
UVALive 3942 Remember the Word Tire+DP
查看>>
从微软的DBML文件中我们能学到什么(它告诉了我们什么是微软的重中之重)~目录...
查看>>
被需求搞的一塌糊涂,怎么办?
查看>>
c_数据结构_队的实现
查看>>
jquery 选择器总结
查看>>
Qt设置背景图片
查看>>
【阿里云文档】常用文档整理
查看>>
java中的Volatile关键字
查看>>
前端自定义图标
查看>>
Vagrant的一个BUG - 不支持'change_host_name'
查看>>
实验二
查看>>
独立开发一个云(PaaS)的核心要素, Go, Go, Go!!!
查看>>
MyBatis使用DEMO及cache的使用心得
查看>>