「Luogu1345」[USACO5.4]奶牛的电信Telecowmunication

problem

Solution

题目要求找到最小数量的若干个点，使得这些点被去掉之后，点\(c_1\)和\(c_2\)不连通。

与最小割模型十分类似，考虑转化

约定\((u,v,f)\)表示\(u\)向\(v\)连边，流量为\(f\)，\(S\)为源，\(T\)为汇

先说模型

对于每个点\(u\)，将其拆成\(u\times2,u\times2+1\)两个点，建边\((u\times2,u\times2+1,1)\)

对于原图上的每条边\((u,v)\)，建边\((u\times2+1,v\times2,inf)\)

最后令\(S=c_1\times2+1,T=c_2\times2\)，求出最小割即可

为什么这样建模？

首先我们割的是点而不是边，我们需要在模型中将这个决策体现出来，因此需要将点拆成一个“入点”和一个“出点”。
去掉每个点对答案的贡献为\(1\)，所以入点和出点之间连一条流量为\(1\)的边。割掉这条边的意义即为去掉了这个点。

然后对于原图上的无向边，可以视作两条方向相反的有向边
对于每条有向边\((u,v)\)，相当于是从\(u\)“出来”，“进入”了\(v\)，所以从\(u\)对应的出点向\(v\)对应的入点连边，流量为正无穷

由于我们是从\(c_1\)出发到达\(c_2\)，所以源是\(c_1\)对应的出点，汇是\(c_2\)对应的入点

显然最小割一定只包括流量为\(1\)的边

Code

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define i(u) ((u)<<1)//入
#define o(u) (((u)<<1)|1)//出
using namespace std;
typedef long long ll;

template <typename T> void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int inf=0x3f3f3f3f;
const int maxn=1005,maxm=6005;
int n,m;
int S,T,c1,c2;
int ans;
 
struct edge
{
    int u,v,f,nxt;
}g[maxm*2];

int head[maxn],ecnt=1;
void eADD(int u,int v,int f)
{
//  cerr<<u<<" "<<v<<" "<<f<<endl;
    g[++ecnt].u=u;g[ecnt].v=v;g[ecnt].f=f;g[ecnt].nxt=head[u];head[u]=ecnt;
    g[++ecnt].u=v;g[ecnt].v=u;g[ecnt].f=0;g[ecnt].nxt=head[v];head[v]=ecnt;
}

int dep[maxn];
bool BFS()
{
    queue<int> q;
    memset(dep,0,sizeof(dep));
    dep[S]=1;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();    
        for(register int i=head[u];i;i=g[i].nxt)
        {
            int v=g[i].v;
            if(!dep[v] && g[i].f)
            {
                dep[v]=dep[u]+1;
                if(v==T)return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int u,int infl)
{
    if(u==T)return infl;
    int rest=infl;
    for(register int i=head[u];i && rest;i=g[i].nxt)
    {
        int v=g[i].v;
        if(dep[v]==dep[u]+1 && g[i].f)
        {
            int flow=dfs(v,min(g[i].f,rest));
            rest-=flow;
            g[i].f-=flow;
            g[i^1].f+=flow;
        }
    }
    return infl-rest;
}

int main()
{
    read(n),read(m),read(c1),read(c2);
    for(register int i=1;i<=n;++i)
        eADD(i(i),o(i),1);
    for(register int i=1;i<=m;++i)
    {
        int u,v;
        read(u),read(v);
        eADD(o(u),i(v),inf);
        eADD(o(v),i(u),inf);
    }
    S=o(c1),T=i(c2);
    while(BFS())
        ans+=dfs(S,inf);
    printf("%d",ans);
    return 0;
}

「Luogu1345」[USACO5.4]奶牛的电信Telecowmunication