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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=,inf=;
struct ee{int to,next,f;}e[N*N*];
int S,T,cnt=,n,k,timer,m,u,v,w,a1,a2,an,b1,b2,bn;
char s[N];
long long ans;
int head[N],dis[N],pre[N],q[N],map[N][N];
bool inq[N];
void ins(int u,int v,int f){
e[++cnt].to=v,e[cnt].next=head[u],e[cnt].f=f,head[u]=cnt;
e[++cnt].to=u,e[cnt].next=head[v],e[cnt].f=,head[v]=cnt;
}
bool bfs(){
for (int i=;i<=T;i++) dis[i]=inf;
int h=,t=,now;
q[]=S;dis[S]=;
while(h!=t){
now=q[++h];
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[now]+<dis[v]){
dis[v]=dis[now]+;
if (v==T)return ;
q[++t]=v;
}
}
}
if (dis[T]==inf) return ; return ;
} int dinic(int now,int f){
if (now==T) return f;
int rest=f;
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[v]==dis[now]+){
int t=dinic(v,min(rest,e[i].f));
if (!t) dis[v]=;
e[i].f-=t;
e[i^].f+=t;
rest-=t;
}
}
return f-rest;
} void build(){
memset(head,,sizeof(head));cnt=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(map[i][j]==) ins(i,j,);
if(map[i][j]==) ins(i,j,inf);
}
} int main(){
while(scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF){
a1++;a2++;b1++;b2++;
memset(map,,sizeof(map));
bool flag=;ans=;
T=;
for(int i=;i<=n;i++){
scanf("%s",s+);
for(int j=;j<=n;j++){
if(s[j]=='O') map[i][j]=;
if(s[j]=='N') map[i][j]=;
}
}
build();
ins(S,a1,an*);ins(a2,T,an*);
ins(S,b1,bn*);ins(b2,T,bn*);
while(bfs())
ans+=dinic(S,inf);
if (ans<(bn+an)*) flag=;
if(!flag){
ans=;
build();
ins(S,a1,an*);ins(a2,T,an*);
ins(S,b2,bn*);ins(b1,T,bn*);
while(bfs())
ans+=dinic(S,inf);
if (ans<(bn+an)*) flag=;
}
if(flag) printf("No\n");else printf("Yes\n");
}
}