[CQOI2014]危桥

题目链接：[CQOI2014]危桥

因为来回an和bn次，就相当于过去2an和2bn次。

一般人都会之间按照题目建图，如果是危桥就流量为2，然后如果是普通桥就流量为inf。

但是这样有一个问题，如果是a1的流量到b2，b1的流量到a2就会有问题。

但是如果我们交换b1和b2之后也是满流则答案正确，我们画图设a1流到b2的流量为x可得，如果也是满流，那么a1一定也可以到a2.

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10,M=1e5+10;
int n,a1,a2,an,b1,b2,bn,s,t,h[N];
int head[N],nex[M],to[M],w[M],tot;
char g[55][55];
inline void ade(int a,int b,int c){
    to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
    ade(a,b,c); ade(b,a,0);
}
inline void init(){
    tot=1;  memset(head,0,sizeof head); s=0;    t=n+1;
}
inline int bfs(){
    memset(h,0,sizeof h);   h[s]=1; queue<int> q;   q.push(s);
    while(q.size()){
        int u=q.front();    q.pop();
        for(int i=head[u];i;i=nex[i]){
            if(w[i]&&!h[to[i]]){
                h[to[i]]=h[u]+1;    q.push(to[i]);
            }
        }
    }
    return h[t];
}
int dfs(int x,int f){
    if(x==t)    return f; int fl=0;
    for(int i=head[x];i&&f;i=nex[i]){
        if(w[i]&&h[to[i]]==h[x]+1){
            int mi=dfs(to[i],min(w[i],f));
            w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
        }
    }
    if(!fl) h[x]=-1;
    return fl;
}
inline int dinic(){
    int res=0;
    while(bfs())    res+=dfs(s,inf);
    return res;
}
int main(){
    while(~scanf("%d %d %d %d %d %d %d",&n,&a1,&a2,&an,&b1,&b2,&bn)){
        a1++; a2++; b1++; b2++; //an*=2; bn*=2;
        init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                char x; cin>>x; if(x=='O')  add(i,j,1); else if(x=='N') add(i,j,inf);   g[i][j]=x;
            }
        }
        add(s,a1,an);   add(a2,t,an); add(s,b1,bn); add(b2,t,bn);
        int res1=dinic();
        init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(g[i][j]=='O')  add(i,j,1); else if(g[i][j]=='N') add(i,j,inf);
            }
        }
        swap(b1,b2);
        add(s,a1,an);   add(a2,t,an); add(s,b1,bn); add(b2,t,bn);
        int res2=dinic();
        puts(min(res1,res2)==an+bn?"Yes":"No");
    }
    return 0;
}