Alice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双
向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？
Alice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双
向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？
本题有多组测试数据。
每组数据第一行包含7个空格隔开的整数，分别为N、al、a2、an、bl、b2、bn。
接下来是一个N行N列的对称矩阵，由大写字母组成。矩阵的i行j列描述编号i一1和j-l的岛屿间的连接情况，若为“O”则表示有危桥相连：为“N”表示有普通的桥相连：为“X”表示没有桥相连。
|
对于每组测试数据输出一行，如果他们都能完成愿望输出“Yes”，否则输出“No”。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=55,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } int n,a1,a2,an,b1,b2,bn,s,t; int g[N][N]; int tot; char ss[N]; struct edge{ int v,ne,c,f; }e[N*N<<1]; int cnt,h[N]; inline void ins(int u,int v,int c){ cnt++; e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt; } int q[N],head,tail,vis[N],d[N]; bool bfs(){ memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); head=tail=1; q[tail++]=s;d[s]=0;vis[s]=1; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1; d[v]=d[u]+1; if(v==t) return true; q[tail++]=v; } } } return false; } int cur[N]; int dfs(int u,int a){ if(u==t||a==0) return a; int flow=0,f; for(int &i=cur[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){ flow+=f; e[i].f+=f; e[((i-1)^1)+1].f-=f; a-=f; if(a==0) 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 th[N],tc; bool solve(){ s=0;t=n+1; ins(s,a1,an);ins(s,b1,bn); ins(a2,t,an);ins(b2,t,bn); int ans=dinic();//printf("ans1 %d\n",ans); if(ans!=an+bn) return false; cnt=0;memset(h,0,sizeof(h)); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(g[i][j]) ins(i,j,g[i][j]); ins(s,a1,an);ins(s,b2,bn); ins(a2,t,an);ins(b1,t,bn); ans=dinic();//printf("ans2 %d\n",ans); if(ans!=an+bn) return false; return true; } int main(){ //freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF){ a1=read()+1;a2=read()+1;an=read()*2; b1=read()+1;b2=read()+1;bn=read()*2; cnt=0;memset(h,0,sizeof(h)); for(int i=1;i<=n;i++){ scanf("%s",ss+1); for(int j=i+1;j<=n;j++){ if(ss[j]==‘O‘) ins(i,j,2),g[i][j]=2; else if(ss[j]==‘N‘) ins(i,j,INF),g[i][j]=INF; else g[i][j]=0; } } if(solve()) puts("Yes"); else puts("No"); } }
原文：http://www.cnblogs.com/candy99/p/6241419.html