题目描述

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“。

 

输入输出样例

输入样例#1：

4 0 1 1 2 3 1XOXXOXOXXOXOXXOX4 0 2 1 1 3 2XNXONXOXXOXOOXOX

输出样例#1：

YesNo数据范围 4

说明

4<=N<50

0<=a1, a2, b1, b2<=N-1

1 <=an. b<=50

思路：正反跑最大流

代码实现：

1 #include
     
       2 #include
      
        3 const int maxn=60; 4 const int inf=1e6; 5 int n,a1,a2,an,b1,b2,bn,s,t; 6 char map[maxn][maxn]; 7 inline int min_(int x,int y){
   return x
       
        tail){21         a=q[tail++];22         for(int i=h[a];i;i=e[i].n)23         if(!d[e[i].s]&&e[i].w){24             d[e[i].s]=d[a]+1;25             if(e[i].s==t) return;26             q[head++]=e[i].s;27         }28     }29 }30 int ap(int k,int w){31     if(k==t) return w;32     int uw=w;33     for(int i=h[k];i&&uw;i=e[i].n)34     if(d[e[i].s]==d[k]+1&&e[i].w){35         int nw=ap(e[i].s,min_(uw,e[i].w));36         if(nw) e[i].w-=nw,e[i^1].w+=nw,uw-=nw;37         else d[e[i].s]=0;38     }39     return w-uw;40 }41 void Dinic(){
   while(bfs(),d[t]) wt+=ap(s,inf);}42 int main(){43     for(;scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF;wt==2*(an+bn)?puts("Yes"):puts("No")){44         memset(h,0,sizeof(h));45         hs=1,wt=0;    46         s=n,t=s+1;47         for(int i=0;i
       
      
     

我竟然傻逼的没有意识到图是对角线对称的。

题目来源：洛谷