[CQOI2014]危桥

Description:

Alice 和 Bob 居住在一个由 \(N\) 座岛屿组成的国家，岛屿被编号为 \(0\) 到 \(N-1\)。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。
Alice 希望在岛屿 \(a_1\) 和 \(a_2\) 之间往返 \(a_n\) 次（从 \(a1\) 到 \(a2\) 再从 \(a2\) 到 \(a1\) 算一次往返）。同时，Bob 希望在岛屿 \(b_1\) 和 \(b_2\) 之间往返 \(b_n\) 次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问 Alice 和 Bob 能完成他们的愿望吗？

Solution:

这题的网络流建模是裸的,没什么好说的,主要在于一个细节

虽然我们最大流跑得\(Ans=a_n+b_n\) ,但是依然可能无解

因为可能有a的流跑到b的汇点去了,然后b的流跑了过来

那么怎么办呢? 把b的汇点原点交换,再跑一次就可以了

两次答案都满足才有解(可以在草稿纸上模拟一下)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll mxn=1e5+5,inf=1e17;
ll a1,a2,b1,b2,an,bn,c0,c1,s0,s1,n,m,cnt,ans,hd[mxn];
ll a[55][55],col[55][55];
ll dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};
char mp[500][500];

inline ll read() {
    char c=getchar(); ll x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(ll &x,ll y) {if(xy) x=y;}

struct ed {
    ll to,nxt,w;
}t[mxn<<1];

inline void add(ll u,ll v,ll w) {
    t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
    t[++cnt]=(ed) {u,hd[v],0}; hd[v]=cnt;
}

ll S,T,cur[mxn],dep[mxn];

ll bfs() {
    memset(dep,0,sizeof(dep)); dep[S]=1;
    queue q; q.push(S); 
    for(ll i=S;i<=T;++i) cur[i]=hd[i];
    while(!q.empty()) {
        ll u=q.front(); q.pop();
        for(ll i=hd[u];i!=-1;i=t[i].nxt) {
            ll v=t[i].to;
            if(!dep[v]&&t[i].w>0) 
                dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[T];
}

ll dfs(ll u,ll f) {
    if(u==T) return f;
    for(ll &i=cur[u];i!=-1;i=t[i].nxt) {
        ll v=t[i].to;
        if(t[i].w>0&&dep[v]==dep[u]+1) {
            ll tp=dfs(v,min(f,t[i].w));
            if(tp>0) {
                t[i].w-=tp;
                t[i^1].w+=tp;
                return tp;
            }
        }
    }
    return 0;
} 

void Dinic() {
    while(bfs()) 
        while(ll tp=dfs(S,inf)) 
            ans+=tp;
}

int check() {
    T=n*n+1;
    memset(hd,-1,sizeof(hd)); cnt=-1; ans=0;
    add(S,a1,an); add(S,b1,bn);
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n;++j) {
            if(mp[i][j]=='X') continue ;
            if(mp[i][j]=='N') add(i,j,inf);
            else add(i,j,2);
        }
    add(a2,T,an); add(b2,T,bn);
    Dinic(); int res1=ans;
    
    memset(hd,-1,sizeof(hd)); cnt=-1; ans=0;
    add(S,a1,an); add(S,b2,bn);
    for(int i=1;i<=n;++i) 
        for(int j=1;j<=n;++j) {
            if(mp[i][j]=='X') continue ;
            if(mp[i][j]=='N') add(i,j,inf);
            else add(i,j,2);
        }
    add(a2,T,an); add(b1,T,bn);
    Dinic(); int res2=ans;
    
    return res1==an+bn&&res2==an+bn;
}

int main() 
{
    while(scanf("%lld",&n)!=EOF) {
        a1=read()+1; a2=read()+1; an=read()*2;
        b1=read()+1; b2=read()+1; bn=read()*2; 
        for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
        check()?puts("Yes"):puts("No");
    }
    return 0;
}
网络流

相关

图论---网络流

网络流 学习笔记

Codeforces 1373F - Network Coverage（模拟网络流）

网络流24题-骑士共存

【网络流24题】最长不下降子序列问题

网络流各算法超详细带源码解析

python 方法无法在线程中使用（附python获取网络流量）

[教程]网络流详解: 从入门到放弃

网络流基础知识

网络流（二）

[知识点]网络流基础

【网络流】CF708D Incorrect Flow

标签