# 【BZOJ 3504】 [Cqoi2014]危桥

## 3504: [Cqoi2014]危桥

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 583 Solved: 309
[Submit][Status][Discuss]
Description

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

Input

|

Output

Sample Input

4 0 1 1 2 3 1

XOXX

OXOX

XOXO

XXOX

4 0 2 1 1 3 2

XNXO

NXOX

XOXO

OXOX

Sample Output

Yes

No

4<=N<50

O<=a1, a2, b1, b2<=N⑴

1 <=an. b<=50

b1,b2交换1下看是不是仍然满流。

#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <cstdio> #include <cstdlib> #include <queue> #define inf 0x3f3f3f3f using namespace std; char S[55][55]; int d[55],v[55],cur[55],tot,s,t,h[55],n,a1,a2,an,b1,b2,bn; struct edge { int from,to,cap,flow,ne; }E[100005]; void Addedge(int from,int to,int cap) { E[++tot]=(edge){from,to,cap,0,h[from]}; h[from]=tot; E[++tot]=(edge){to,from,0,0,h[to]}; h[to]=tot; } void Build() { tot=1; for (int i=s;i<=t;i++) h[i]=0; for (int i=1;i<=n;i++) for (int j=0;j<n;j++) { if (S[i][j]=='O') Addedge(i,j+1,2); if (S[i][j]=='N') Addedge(i,j+1,inf); } } bool bfs() { for (int i=s;i<=t;i++) v[i]=0; queue<int> q; q.push(s); v[s]=1; d[s]=0; while (!q.empty()) { int x=q.front(); q.pop(); for (int i=h[x];i;i=E[i].ne) { edge e=E[i]; if (!v[e.to]&&e.cap>e.flow) { v[e.to]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return v[t]; } int dfs(int x,int a) { if (x==t||!a) return a; int flow=0; for (int &i=cur[x];i;i=E[i].ne) { edge &e=E[i]; if (d[e.to]!=d[x]+1) continue; int f=dfs(e.to,min(a,e.cap-e.flow)); if (f>0) { e.flow+=f; E[i^1].flow-=f; flow+=f; a-=f; if (!a) break; } } return flow; } int dinic() { int flow=0; while (bfs()) { for (int i=s;i<=t;i++) cur[i]=h[i]; flow+=dfs(s,inf); } return flow; } int main() { while (scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF) { s=0,t=n+1; for (int i=1;i<=n;i++) scanf("%s",S[i]); an*=2,bn*=2; a1++,a2++,b1++,b2++; Build(); Addedge(s,a1,an),Addedge(a2,t,an); Addedge(s,b1,bn),Addedge(b2,t,bn); if (dinic()==an+bn) { Build(); Addedge(s,a1,an),Addedge(a2,t,an); Addedge(s,b2,bn),Addedge(b1,t,bn); if (dinic()==an+bn) puts("Yes"); else puts("No"); } else puts("No"); } return 0; } 

### 感悟：

1.TLE是在bfs中没有写v[s]=1

2.CQOI2014题解

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！