[CQOI2014]危桥

墨蓝 2021-11-13 15:38 161阅读 0赞

[\[CQOI2014\]危桥][CQOI2014]

有点神仙的最大流

[ 在Ta的博客查看][Ta]

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

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

每个边也不会走大于1次

#include<bits/stdc++.h>
    #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<<endl
    using namespace std;
    typedef long long ll;
    template<class T>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<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>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*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10803438.html

[CQOI2014]: https://www.luogu.org/problemnew/show/P3163
[Ta]: https://www.luogu.org/blog/39887/solution-p3163