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
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
No
数据范围
4<=N<50
O<=a1, a2, b1, b2<=N-1
1 <=an. b<=50
Solution
这题的关键是跑完最大流后可能是从A1出发的流跑到了B2去，这样就会有问题。
所以我们交换B1,B2再跑一遍最大流，如果依旧满流即可行。
可以发现设第一次跑最大流时A1->A2流了x，A1->B2流了2*An-x，B1->B2流了2*Bn-(2*An-x)。
那么交换B1,B2后因为是无向图，所以A1->A2仍然流了x，A1->B1流了2*An-x。
即A1->B2->B1流了2*An-x，所以即B1->B2流了2*Bn。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=100,M=20000; int n,a1,a2,an,b1,b2,bn,S,T,tot,Next[M],head[N],tree[M],val[M],Queue[N],h[N],cur[N]; char s[60][60]; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void add_edge(int x,int y,int z) { add(x,y,z); add(y,x,0); } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); Queue[1]=S;h[S]=0; while (t!=w) { int u=Queue[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]>0) { int v=tree[i]; if (h[v]==-1) { h[v]=h[u]+1; Queue[++w]=v; } } } return h[T]!=-1; } int dfs(int u,int low) { if (u==T) return low; int used=0; for (int i=cur[u];i;i=Next[i]) if (val[i]>0) { int v=tree[i]; if (h[v]==h[u]+1) { int w=dfs(v,min(low-used,val[i])); used+=w; val[i]-=w;val[i^1]+=w; cur[u]=i; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=T;i++) cur[i]=head[i]; ans+=dfs(S,1<<29); } return ans; } void Pre() { tot=1; memset(head,0,sizeof(head)); add_edge(S,a1,an*2); add_edge(S,b1,bn*2); add_edge(a2,T,an*2); add_edge(b2,T,bn*2); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (s[i][j]=='O') add_edge(i,j,2); if (s[i][j]=='N') add_edge(i,j,1<<29); } } int main() { while (scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF) { a1++;a2++;b1++;b2++; S=n+1;T=n+2; for (int i=1;i<=n;i++) scanf("%s",s[i]+1); Pre(); int Ans=dinic(); if (Ans!=an*2+bn*2) { puts("No");continue;} swap(b1,b2); Pre(); Ans=dinic(); if (Ans!=an*2+bn*2) puts("No");else puts("Yes"); } return 0; } |
