3504: [Cqoi2014]危桥

3504: [Cqoi2014]危桥

Time Limit: 10 Sec   Memory Limit: 128 MB Submit: 1306   Solved: 651 [ Submit][ Status][ Discuss]

Description

Alice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双 向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？

Input

本题有多组测试数据。 每组数据第一行包含7个空格隔开的整数，分别为N、al、a2、an、bl、b2、bn。 接下来是一个N行N列的对称矩阵，由大写字母组成。矩阵的i行j列描述编号i一1和j-l的岛屿间的连接情况，若为“O”则表示有危桥相连：为“N”表示有普通的桥相连：为“X”表示没有桥相连。 |

Output

对于每组测试数据输出一行，如果他们都能完成愿望输出“Yes”，否则输出“No”。

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 1 <=an. b<=50

HINT

Source

[ Submit][ Status][ Discuss] 从a1到a2往返an次 && 从b1到b2往返bn次 有些桥只能走两次 --> 最大流 如果从a1到a2能跑2*an个流量 如果从b1到b2能跑2*bn个流量 说明有解？？？ 不，，，GG 事实上，有些时候a1会跑到b2 解决的办法，，把b1b2交换下再跑就行了 (我也不会证，看大神的题解来着) #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<bitset> #include<algorithm> #include<cstring> #include<map> #include<stack> #include<set> #include<cmath> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 55; const int maxm = 300000; const int INF = ~0U>>1; struct E{ int to,cap,flow; E (int _to = 0,int _cap = 0,int _flow = 0) {to = _to; cap = _cap; flow = _flow;} }edgs[maxm]; int n,tot,cnt,Cnt,S,T = maxm-1,a1,a2,an,b1,b2,bn,L[maxm],cur[maxm],vis[maxm]; char ch[maxn][maxn]; vector <int> v[maxm]; queue <int> Q; void Add(int x,int y,int w) { v[x].push_back(cnt); edgs[cnt++] = E(y,w,0); v[y].push_back(cnt); edgs[cnt++] = E(x,0,0); } void Build() { cnt = 0; tot = n; Add(S,a1,an*2); Add(S,b1,bn*2); Add(a2,T,an*2); Add(b2,T,bn*2); for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) { if (ch[i][j] == 'X') continue; Add(i,++tot,INF); Add(j,tot,INF); if (ch[i][j] == 'N') Add(tot-1,++tot,INF); else Add(tot-1,++tot,2); Add(tot,i,INF); Add(tot,j,INF); } } bool BFS() { vis[S] = ++Cnt; L[S] = 1; Q.push(S); while (!Q.empty()) { int k = Q.front(); Q.pop(); for (int i = 0; i < v[k].size(); i++) { E e = edgs[v[k][i]]; if (e.cap == e.flow) continue; if (vis[e.to] == Cnt) continue; vis[e.to] = Cnt; L[e.to] = L[k] + 1; Q.push(e.to); } } return vis[T] == Cnt; } int Dicnic(int x,int a) { if (x == T || !a) return a; int flow = 0; for (int &i = cur[x]; i < v[x].size(); i++) { E &e = edgs[v[x][i]]; if (e.cap == e.flow) continue; if (L[e.to] != L[x] + 1) continue; int f = Dicnic(e.to,min(a,e.cap - e.flow)); if (!f) continue; a -= f; e.flow += f; edgs[v[x][i]^1].flow -= f; flow += f; } if (!flow) L[x] = -1; return flow; } bool MaxFlow() { int Maxflow = 0; while (BFS()) { for (int i = S; i <= tot; i++) cur[i] = 0; cur[T] = 0; Maxflow += Dicnic(S,INF); } for (int i = S; i <= tot; i++) v[i].clear(); v[T].clear(); return Maxflow == 2*(an + bn); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif while (scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn) != EOF) { ++a1; ++a2; ++b1; ++b2; for (int i = 1; i <= n; i++) scanf("%s",ch[i] + 1); Build(); bool flag1 = MaxFlow(); if (!flag1) {puts("No"); continue;} swap(b1,b2); Build(); bool flag2 = MaxFlow(); if (!flag2) {puts("No"); continue;} puts("Yes"); } return 0; }