「题解」「CQOI2014」危桥 bridge

一道 网络流 的简单题,2014 年 CQOI 的省选题。

题目链接:Luogu P3163/BZOJ 3504/LibreOJ 2239/CQOI2014 D1T2。

题目

题意简述

有一个 $n$ 个点的图,点的编号从 $0$ 到 $n-1$。有些边可以通过无限次,有的只能通过两次。Alice 希望在点 $a _ 1$ 和 $a _ 2$ 之间往返 $a _ n$ 次。同时,Bob 希望在点 $b _ 1$ 和 $b _ 2$ 之间往返 $b _ n$次。请问 Alice 和 Bob 能完成他们的愿望吗?

这道题有多组数据。

数据范围

变量数据范围
$n$$4\leq n\leq 49$
$a _ n,b _ n$$1\leq a_n,b_n\leq 50$

时空限制

题目时间限制空间限制
Luogu P3163$$1\text{s}$$$$125\text{MiB}$$
BZOJ 3504$$10\text{s}$$$$128\text{MiB}$$
LibreOJ 2239$$1\text{s}$$$$256\text{MiB}$$
CQOI2014 D1T2$$1\text{s}$$$$256\text{MiB}$$

题解

思路

首先发现,往返中返的部分可以倒过来,所以在点 $a_1$ 和 $a_2$ 之间往返 $a_n$ 次相当于从 $a_1$ 可以到 $a_2$ 至少 $2\times a_n$ 次。

所以发现是网络流。

只能通过 $2$ 次的边的边权设置成 $2$,其他的边的边权设置成 $+\infty$。

从 $s$ 向 $a_1$ 连一条 $2\times a_n$ 的边,从 $a_2$ 向 $t$ 连一条 $2\times a_n$ 的边。
从 $s$ 向 $b_1$ 连一条 $2\times b_n$ 的边,从 $b_2$ 向 $t$ 连一条 $2\times b_n$ 的边。

但是这样可能会有 $a_1$ 的流量跑到 $b_2$ 那,所以还要建一个:

从 $s$ 向 $a_1$ 连一条 $2\times a_n$ 的边,从 $a_2$ 向 $t$ 连一条 $2\times a_n$ 的边。
从 $s$ 向 $b_2$ 连一条 $2\times b_n$ 的边,从 $b_1$ 向 $t$ 连一条 $2\times b_n$ 的边。

然后就解决了这一题。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F //定义正无穷
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=50+5;

inline void Read(void);
inline void Work(void);

int n;

int main(void){
    while(scanf("%d",&n)!=EOF){ //这道题有多组数据
        Read();
        Work();
    }
    return 0;
}

int s,t;
int a1,a2,an;
int b1,b2,bn;
int cnt,head[MAXN],to[(MAXN*MAXN)<<1],w[(MAXN*MAXN)<<1],Next[(MAXN*MAXN)<<1];

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len){
    Add_Edge(u,v,len);
    Add_Edge(v,u,0);
    return;
}

char M[MAXN][MAXN];

inline void Read(void){
    a1=read()+1,a2=read()+1,an=read(),b1=read()+1,b2=read()+1,bn=read();
    //注意处理编号
    for(reg int i=1;i<=n;++i)
        scanf("%s",M[i]+1); //读入
    return;
}

int dep[MAXN];
queue<int> Q;

inline bool BFS(int s,reg int t){ //分层图
    memset(dep,-1,sizeof(dep));
    while(!Q.empty())Q.pop();
    dep[s]=1,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        for(reg int i=head[ID];i;i=Next[i])
            if(dep[to[i]]==-1&&w[i]>0){
                dep[to[i]]=dep[ID]+1;
                Q.push(to[i]);
            }
    }
    return dep[t]!=-1;
}

int cur[MAXN];

inline int DFS(reg int ID,reg int t,reg int lim){ //找增广路
    if(ID==t)
        return lim;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i])
        if(dep[to[i]]==dep[ID]+1&&w[i]>0){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f;
                w[i]-=f;
                w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    return flow;
}

inline int Dinic(reg int s,reg int t){ //求最大流
    reg int res=0;
    while(BFS(s,t)){
        memcpy(cur,head,sizeof(head));
        res+=DFS(s,t,INF);
    }
    return res;
}

inline void Build(void){
    cnt=1; //初始化 cnt
    memset(head,0,sizeof(head)); //初始化 head[]
    s=0,t=n+1; //设置源点 s 和 汇点 t
    for(reg int i=1;i<=n;++i)
        for(reg int j=1;j<=n;++j)
            if(i!=j)
                switch(M[i][j]){ //加边
                    case 'N':Add_Tube(i,j,INF);break;
                    case 'O':Add_Tube(i,j,2);break;
                    default:break;
                }
    return;
}

inline void Work(void){
    Build();
    Add_Tube(s,a1,an*2),Add_Tube(a2,t,an*2);
    Add_Tube(s,b1,bn*2),Add_Tube(b2,t,bn*2);
    reg int ans1=Dinic(s,t); //第一种方式
    Build();
    Add_Tube(s,a1,an*2),Add_Tube(a2,t,an*2);
    Add_Tube(s,b2,bn*2),Add_Tube(b1,t,bn*2);
    reg int ans2=Dinic(s,t); //第二种方式
    puts(ans1==(an+bn)*2&&ans2==(an+bn)*2?"Yes":"No");
    return;
}