题解 P3163 【[CQOI2014]危桥】

UltiMadow · 2020-08-05 16:51:51 · 题解

update on 2024.6.10: 把剪切板的内容搬到了正文中。

先来一个结论：

首先建出给定的网络流图，危桥容量为 2，其他容量为 +\infty，然后建出超级源点 s,t；

接着连 s\to a_1，容量为 2\times a_n；连 s\to b_1，容量为 2\times b_n；连 a_2\to t，容量为 2\times a_n；连 b_2\to t，容量为 2\times b_n，并跑一遍最大流；

接下来连 s\to a_1，容量为 2\times a_n；连 s\to b_2，容量为 2\times b_n；连 a_2\to t，容量为 2\times a_n；连 b_1\to t，容量为 2\times b_n，并跑一遍最大流；

若这两遍最大流跑出来的结果均为 2\times(a_n+b_n) 则结果为 Yes，否则为 No。

证明如下：

对于网络流来说，对于每条边有一个不等式，对于每个点有一个流量平衡的方程。

我们记 f_A(u,v) 为 A 走 u\to v 这条边多少次；f_B(u,v) 为 B 走 u\to v 这条边多少次，根据网络流的思想，有 f(u,v)=-f(v,u)。

有不等式：

令 f_1=f_A+f_B,f_2=f_A-f_B，

等式：

接下来：

于是能解出 f_1,f_2 就能一一对应地求出 f_A,f_B。

发现 f_1 即为第一遍网络流的结果，f_2 即为第二遍网络流的结果，于是跑两遍上述网络流即可。

接下来，我们又得到了几个结论：

1. 这题不可以扩展到有向图上，因为扩展到有向图上之后第一步的不等式转化并不成立；
2. 这题不可以扩展到多于两个「小朋友」，因为找不到 f_A,f_B 与 f_1,f_2 这种变换了；
3. 这题不可以扩展到一条「危桥」能走奇数次，因为这样解出来的 f_1,f_2 可能不为整数。

code:

#include<bits/stdc++.h>
#define MAXN 1010
#define inf 0x3f3f3f3f
using namespace std;
int n;
int sa,ta,an,sb,tb,bn;
struct Node{int to,nxt,flow;}Edge[MAXN<<4],sav[MAXN<<4];
int Head[MAXN],cnt_Edge;
int head[MAXN],cnt_edge;
void add(int u,int v,int w){
    sav[++cnt_edge]=(Node){v,head[u],w};
    head[u]=cnt_edge;
}
void add_edge(int u,int v,int w){add(u,v,w);add(v,u,0);}
void Add(int u,int v,int w){
    Edge[++cnt_Edge]=(Node){v,Head[u],w};
    Head[u]=cnt_Edge;
}
void Add_Edge(int u,int v,int w){Add(u,v,w);Add(v,u,0);}
int nhe[MAXN<<1],dep[MAXN<<1];
int q[MAXN<<2];
bool bfs(int s,int t){
    int l=1,r=1;q[1]=s;
    memset(dep,0,sizeof(dep));
    memcpy(nhe,Head,sizeof(nhe));
    dep[s]=1;
    while(l<=r){
        int u=q[l++];
        for(int i=Head[u];i;i=Edge[i].nxt){
            int v=Edge[i].to,w=Edge[i].flow;
            if(!w||dep[v])continue;
            dep[v]=dep[u]+1;q[++r]=v;
            if(v==t)return true;
        }
    }return false;
}
int dfs(int u,int t,int flow){
    int rest=flow;if(u==t)return flow;
    for(int i=nhe[u];i&&rest;i=Edge[i].nxt){
        int v=Edge[i].to,w=Edge[i].flow;nhe[u]=i;
        if(!w||dep[v]!=dep[u]+1)continue;
        int now=dfs(v,t,min(rest,w));
        if(!now)dep[v]=-1;
        Edge[i].flow-=now;Edge[i^1].flow+=now;
        rest-=now;
    }return flow-rest;
}
int dinic(int s,int t){
    int ret=0;
    while(bfs(s,t)){
        int flow;
        while((flow=dfs(s,t,inf)))
            ret+=flow;
    }return ret;
}
char c[MAXN];
int main(){
    while(scanf("%d%d%d%d%d%d%d",&n,&sa,&ta,&an,&sb,&tb,&bn)!=EOF){
        sa++;ta++;sb++;tb++;cnt_edge=1;
        for(int i=1;i<=n;i++){
            scanf("%s",c+1);
            for(int j=1;j<=n;j++){
                if(c[j]=='O')add_edge(i,j,2);
                if(c[j]=='N')add_edge(i,j,inf);
            }
        }
        memcpy(Head,head,sizeof(Head));cnt_Edge=cnt_edge;
        for(int i=2;i<=cnt_edge;i++)Edge[i]=sav[i];
        int s=n+1,t=n+2;
        Add_Edge(s,sa,2*an);Add_Edge(s,sb,2*bn);
        Add_Edge(ta,t,2*an);Add_Edge(tb,t,2*bn);
        int now=dinic(s,t);bool ans=false;
        if(now==2*(an+bn))ans=true;
        memcpy(Head,head,sizeof(Head));cnt_Edge=cnt_edge;
        for(int i=2;i<=cnt_edge;i++)Edge[i]=sav[i];
        Add_Edge(s,sa,2*an);Add_Edge(s,tb,2*bn);
        Add_Edge(ta,t,2*an);Add_Edge(sb,t,2*bn);
        now=dinic(s,t);bool ans2=false;
        if(now==2*(an+bn))ans2=true;
        ans=(ans&&ans2);
        printf("%s\n",ans?"Yes":"No");
        memset(Head,0,sizeof(Head));memset(head,0,sizeof(head));
        for(int i=2;i<=cnt_Edge;i++)sav[i]=(Node){0,0,0};
        for(int i=2;i<=cnt_Edge;i++)Edge[i]=(Node){0,0,0};
        cnt_Edge=cnt_edge=1;
    }
    return 0;
}