有点神仙的最大流

就是这样做，(F1+F2)/2后对应a的走法，(F1-F2)/2后对应b的走法

可以拼凑出合法的增广路，并且两者不会相交（整体除以2容量认为是1）。

每个边也不会走大于1次

 

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=105;const int inf=0x3f3f3f3f;int n,a1,a2,an,b1,b2,bn;int s,t;struct node{    int nxt,to,w;}e[2*(N*N)];int hd[N],cnt=1;char mp[N][N];void add(int x,int y,int z){    e[++cnt].nxt=hd[x];    e[cnt].to=y;e[cnt].w=z;    hd[x]=cnt;    e[++cnt].nxt=hd[y];    e[cnt].to=x;e[cnt].w=0;    hd[y]=cnt;}int d[N];int dfs(int x,int flow){    if(x==t) return flow;    int res=flow;    for(reg i=hd[x];i&&res;i=e[i].nxt){        int y=e[i].to;        if(e[i].w&&d[y]==d[x]+1){            int k=dfs(y,min(res,e[i].w));            if(!k) d[y]=0;            e[i].w-=k;            e[i^1].w+=k;            res-=k;        }    }    return flow-res;}int q[N],l,r;bool bfs(){    memset(d,0,sizeof d);    l=1,r=0;    q[++r]=s;    d[s]=1;    while(l<=r){        int x=q[l++];        for(reg i=hd[x];i;i=e[i].nxt){            int y=e[i].to;            if(e[i].w&&!d[y]){                d[y]=d[x]+1;                if(y==t) return true;                q[++r]=y;            }        }    }    return false;}void clear(){    memset(hd,0,sizeof hd);    cnt=1;}int main(){    while(scanf("%d",&n)!=EOF){        rd(a1);rd(a2);rd(an);rd(b1);rd(b2);rd(bn);        ++a1,++a2,++b1,++b2;        clear();        s=0;t=n+1;        for(reg i=1;i<=n;++i){            scanf("%s",mp[i]+1);            for(reg j=1;j<=n;++j){                if(mp[i][j]=='O'){                    add(i,j,1);                }else if(mp[i][j]=='N'){                    add(i,j,inf);                }            }        }        add(s,a1,an);add(a2,t,an);        add(s,b1,bn);add(b2,t,bn);        int flow=0,ans=0;        while(bfs()){            while(flow=dfs(s,inf)) ans+=flow;        }        clear();        s=0;t=n+1;        for(reg i=1;i<=n;++i){            for(reg j=1;j<=n;++j){                if(mp[i][j]=='O'){                    add(i,j,1);                }else if(mp[i][j]=='N'){                    add(i,j,inf);                }            }        }        add(s,a1,an);add(a2,t,an);        add(s,b2,bn);add(b1,t,bn);        flow=0;        while(bfs()){            while(flow=dfs(s,inf)) ans+=flow;        }        if(ans==2*(an+bn)){            puts("Yes");        }else puts("No");    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle**/