「BZOJ3504」[CQOI2014] 危桥
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”表示没有桥相连。
|
每组数据第一行包含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
题解
网络流即可。。。但是只做一遍会有问题：比如从a1万一到不了a2,然而最终流到了b2，这样显然是不可行的。那么我们可以把b1和b2反一下再做一遍，如果还是满流就可以了。
|
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 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long #define T 51 using namespace std; bool flag; int n,a1,a2,an,b1,b2,bn; int cnt,ans; int h[55],q[55]; int mp[55][55]; struct data{int to,next,v;}e[100005];int head[55],cur[55]; void ins(int u,int v,int w) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} void build() { memset(head,0,sizeof(head));cnt=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]==1)insert(i,j,2); else if(mp[i][j]==2)insert(i,j,inf); } bool bfs() { int t=0,w=1; for(int i=0;i<=T;i++)h[i]=-1; q[0]=0;h[0]=0; while(t!=w) { int now=q[t];t++; for(int i=head[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[w++]=e[i].to; } } if(h[T]==-1)return 0; return 1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(e[i].v,w)); e[i].v-=w; if(e[i].v)cur[x]=i; e[i^1].v+=w; used+=w;if(used==f)return f; } } if(!used)h[x]=-1; return used; } void dinic() {while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];ans+=dfs(0,inf);}} int main() { while(scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF) { memset(mp,0,sizeof(mp));flag=0; a1++;a2++;b1++;b2++; for(int i=1;i<=n;i++) { char ch[55]; scanf("%s",ch); for(int j=1;j<=n;j++) if(ch[j-1]=='O')mp[i][j]=1; else if(ch[j-1]=='N')mp[i][j]=2; } build(); insert(0,a1,an*2);insert(a2,T,an*2); insert(0,b1,bn*2);insert(b2,T,bn*2); ans=0; dinic(); if(ans<2*(an+bn))flag=1; if(!flag) { build(); insert(0,a1,an*2);insert(a2,T,an*2); insert(0,b2,bn*2);insert(b1,T,bn*2); ans=0; dinic(); if(ans<2*(an+bn))flag=1; } if(flag)printf("No\n"); else printf("Yes\n"); } return 0; } |
黄学长……请问这么建边为何不会出现对于x-y的危桥，x->y先走了2次，然后y->x又走了4次，这样重复下去？
其实你多建立一倍的边