最小割3（二分图）

发布日期: 2022-04-30

最小割3（二分图）

最小权覆盖集

概述

选取任意的点，使得点集可以包含所有的边（每一条边的顶点至少有一个被选择）。

证明

首先进行图的二分然后从S到左边图连一个容量为点权的边，右边图连一个向T容量也为点权的边，中间的点都用inf相连，可以发现构造成了一个简单割。然后证明最小割于最小权覆盖集一一对应。假设有最小割，如果还存在覆盖集那么存在从左边点到右边点的流量，那么不满足最大流，所以冲突；反之假设有覆盖集，我们先选出所有的点集，如果不是最大流，那么还存在流量与覆盖集定义冲突。

Code（acwing 2325）

可以删除出边和入边，所以我们可以直接拆点拆成2个图，然后求最小权覆盖集。

#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=210,M=2e4+10;
int head[N],idx=0;
int n,m,S,T;
int q[N],d[N],cur[N];
bool st[N];
struct Edge{
    int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
    edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
    edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
void dfs(int u)
{
    st[u]=true;
    for(int i=head[u];~i;i=edge[i].next)
        if(edge[i].f&&!st[edge[i].to])
            dfs(edge[i].to);
}
bool bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S,d[S]=0,cur[S]=head[S];
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=head[t];~i;i=edge[i].next)
        {
            int ver=edge[i].to;
            if(d[ver]==-1&&edge[i].f)
            {
                d[ver]=d[t]+1;
                cur[ver]=head[ver];
                if(ver==T)  return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T)    return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
    {
        cur[u]=i;
        int ver=edge[i].to;
        if(d[ver]==d[u]+1&&edge[i].f)
        {
            int t=find(ver,min(edge[i].f,limit-flow));
            if(!t)  d[ver]=-1;
            edge[i].f-=t,edge[i^1].f+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())
        while(flow=find(S,inf))
            res+=flow;
    return res;
}
int main()
{    
    memset(head,-1,sizeof head);
    memset(st,false,sizeof st);
    scanf("%d%d",&n,&m);
    S=0,T=2*n+1;
    for(int i=1;i<=n;i++)
    {
        int w;
        scanf("%d",&w);
        add(S,i,w);
    }
    for(int i=1;i<=n;i++)
    {
        int w;
        scanf("%d",&w);
        add(n+i,T,w);
    }
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(b,n+a,inf);
    }
    printf("%d\n",dinic());
    dfs(S);
    int cnt=0;
    for(int i=0;i<idx;i+=2)
    {
        int a=edge[i^1].to,b=edge[i].to;
        if(st[a]&&!st[b])   cnt++;
    }
    printf("%d\n",cnt);
    for(int i=0;i<idx;i+=2)
    {
        int a=edge[i^1].to,b=edge[i].to;
        if(st[a]&&!st[b]){
            if(a==S)    printf("%d +\n",b);
        }
    }
    for(int i=0;i<idx;i+=2)
    {
        int a=edge[i^1].to,b=edge[i].to;
        if(st[a]&&!st[b]){
            if(b==T)    printf("%d -\n",a-n);
        }
    }
    return 0;
}