网络流初步（2）—— 最小割

最小割

最小割问题可以简单的这样描述：给定一张带权有向图，除去几条边，使 $s$ 到 $t$ 不连通。求去除的边的权值和最小值。

形式化定义一下：对于图 $G=(V,E)$，将点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。我们定义割 $(S,T)$ 的容量为所有从 $S$ 到 $T$ 的边的容量之和，即 $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$，最小割问题就是求一个割，使得割的容量 $c(S,T)$ 最小。

最大流最小割定理

最大流最小割定理：$f(s,t)_{\max}=c(s,t)_{\min}$。

即对于一个网络，其最大流与最小割在数值上相等。我们在处理最小割问题时，直接求最大流即可。

求割边数

洛谷P1344 [USACO4.4]追查坏牛奶Pollutant Control

只需跑一次最大流，然后修改图上边权。对于满流的边容量设为 $1$，没满流的边容量设为 $\infty$，反向边容量设为 $0$，然后再跑一次最大流，得到的就是最小割边数。为了达到这样的操作，我们在加边时多记录一个 x，储存是否是反向边。

 struct Edge{
     int u,v;
     ll c,f;
+    bool x;
 };
 void add_edge(int u,int v,int w){
-    edges.push_back({u,v,0,w});
-    edges.push_back({v,u,0,0});
+    edges.push_back({u,v,w,0,0});
+    edges.push_back({v,u,0,w,1});
     auto m = edges.size();
     G[u].push_back(m-2);
     G[v].push_back(m-1);
}

for(auto& e:edges){
    if(e.x) e.c=0; // 反向边
    else if(e.c==e.f) e.c=1; // 满流
    else e.c=INF;
    e.f=0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 100;
const ll INF = 0x3f3f3f3f3f3f3f;


struct Edge{
    int u,v;
    ll c,f;
    bool x;
};
vector<Edge> edges;
vector<int> G[N];
void add_edge(int u,int v,int w){
    edges.push_back({u,v,w,0,0});
    edges.push_back({v,u,0,w,1});
    auto m = edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}

int s,t;

int d[N];
bool vis[N];
bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);vis[s]=1;d[s]=0;
    while(!q.empty()){
        auto u=q.front();q.pop();
        for(int e:G[u]){
            int v=edges[e].v;
            if(!vis[v] && edges[e].f<edges[e].c){
                vis[v]=1;d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return vis[t];
}

int cur[N];
ll dfs(int u,ll a){
    if(u==t || a==0)return a; //递归返回条件(到汇点了)
    ll ans = 0;
    for(int& i=cur[u];i<G[u].size();i++){
        auto& e=edges[G[u][i]];
        if(d[e.v]==d[u]+1 && e.f<e.c){
            ll f = dfs(e.v,min(a,e.c-e.f));
            ans += f;e.f += f;
            a-=f;edges[G[u][i]^1].f -= f;
            if(a==0)break;
        }
    }
    return ans;
}

ll dinic(){
    ll ans = 0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        ans += dfs(s,INF);
    }
    return ans;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
    }
    s=1,t=n;
    printf("%lld ",dinic());
    for(auto& e:edges){
        if(e.x) e.c=0; // 反向边
        else if(e.c==e.f) e.c=1; // 满流
        else e.c=INF;
        e.f=0;
    }
    printf("%lld\n",dinic());
    return 0;
}

最小割常见模型转化

割点

洛谷P1345 [USACO5.4]奶牛的电信Telecowmunication

题意：给定一张无向图，割 $i$ 个点，使 $s$ 到 $t$ 不连通，求最少割点数。

对于割点问题，我们将一个点拆成两个。对于入边（如下图红色）连接第一个点，对于出边（如下图绿色）连接第二个点，再加入一条第一个点到第二个点的带权有向边（如下图蓝色），权值为该点点权（本题中为1）。对于其他边，边权设为 $\infty$，这样对拆点后图跑最小割即为结果。

AC代码

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int N =  105;


struct Edge{
    int u,v,c,f;
};

vector<Edge> edges;
vector<int> G[2*N];
bool vis[2*N];
int cur[2*N];
int d[2*N];

void add_edge(int u,int v,int w){
    // printf("%d %d %d\n",u,v,w);
    edges.push_back({u,v,w,0});
    edges.push_back({v,u,0,0});
    auto x = edges.size();
    G[u].push_back(x-2);
    G[v].push_back(x-1);
}

int n,m,s,t;


bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    d[s]=0;
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i=0;i<G[u].size();i++){
            auto& e = edges[G[u][i]];
            if(!vis[e.v] && e.f<e.c){
                d[e.v]=d[u]+1;
                vis[e.v]=1;
                q.push(e.v);
            }
        }
    }
    return vis[t];
}

int dfs(int u,int a){
    if(u==t || a==0) return a;
    int flow = 0;
    // printf("dfs %d %lld\n",u,a);
    // printf("\tcur:%d |G[u]|=%llu\n",cur[u],G[u].size());
    for(int &i=cur[u];i<G[u].size();i++){
        auto& e = edges[G[u][i]];
        // printf("%d->%d (%d,%d)\n",u,e.v,d[u],d[e.v]);
        if(d[u]+1 == d[e.v]){
            auto f = dfs(e.v,min(a,e.c-e.f));
            // printf("change %lld\n",f);
            e.f += f;
            edges[G[u][i]^1].f -= f;
            a -= f;
            flow += f;
            if(a==0) break;
        }
    }
    return flow;
}

int dinic(){
    int flow = 0;
    while(bfs()){
        // puts("S");
        memset(cur,0,sizeof(cur));
        flow += dfs(s,INF);
    }
    return flow;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);

    for(int i=1;i<=n;i++){
        if(i==s || i==t) add_edge(i,i+n,INF);
        else add_edge(i,i+n,1);
    }
    t+=n;


    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        // u->v
        // u1->v0
        add_edge(u+n,v,INF);
        add_edge(v+n,u,INF);
    }

    printf("%d\n",dinic());


    return 0;
}

二者选其一问题

洛谷P2057 [SHOI2007] 善意的投票

题意：有 $n$ 个人，划分到两个集合 $A,B$ 中，第 $i$ 个人划分到集合 $A$ 花费 $a_i$，划分到集合 $B$ 花费 $b_i$。有 $m$ 个组合，每个组合有两个人 $u_j,v_j$，若 $u_j,v_j$ 没有划分到同一集合则花费 $w_j$。求最小花费。

我们考虑建模用最小割解决此问题。建图方法是：从源点向每个点连一条边权为 $a_i$ 的边，从每个点向汇点连一条边权为 $b_i$ 的边。在每个组合内，对组合内两个点连边权为 $w_j$ 的双向边。

考虑有三个点，组合有两个，为 $\{1,2\},\{1,3\}$，则建出图如下。

怎么理解这样的建图方法呢？我们回到最小割的实质：将一张图划分为两个点集，使两个点集间连边权值和最小。我们认为，若该点属于 $B$，则与 $s$ 划分到一个集合内，若该点属于 $A$ 则与 $t$ 划分到一个集合内。

我们先来看上图中黄色边：若一个点与 $s$ 划分到一个集合内，则割容量增加它与 $t$ 的边权（即划分到 $B$ 的花费）。若一个点与 $t$ 划分到一个集合内，则割容量增加它与 $s$ 的边权（即划分到 $A$ 的花费）。

再来看蓝色边：若蓝色边的起点和终点划分到了一个集合内，则这条边的边权不会被算入到容量中。若起点和终点划分到了两个集合中，则这条边的边权会被算入到割容量中。

通过这样构造图，我们保证了一个划分的花费恰好等于这个割的容量。因此跑一遍最小割算法就是结果。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long

struct Edge{
    int u,v;
    ll f,c;
};      

const ll INF = 0x3f3f3f3f3f3f3f;
const int N = 305;
vector<Edge> edges;
vector<int> G[N];

void add_edge(int u,int v,int w){
    edges.push_back({u,v,0,w});
    edges.push_back({v,u,0,0});
    auto cnt = edges.size();
    G[u].push_back(cnt-2);
    G[v].push_back(cnt-1);
}

int s,t;

bool vis[N];int d[N];
bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    d[s]=0;
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i=0;i<G[u].size();i++){
            auto& e = edges[G[u][i]];
            if(!vis[e.v] && e.f<e.c){
                d[e.v]=d[u]+1;
                vis[e.v]=1;
                q.push(e.v);
            }
        }
    }
    return vis[t];
}   

int cur[N];
ll dfs(int u,ll a){
    if(u==t || a==0) return a;
    ll flow = 0;
    for(int &i=cur[u];i<G[u].size();i++){
        auto& e = edges[G[u][i]];
        if(d[u]+1 == d[e.v]){
            auto f = dfs(e.v,min(a,e.c-e.f));
            e.f += f;
            edges[G[u][i]^1].f -= f;
            a -= f;
            flow += f;
            if(a==0) break;
        }
    }
    if(flow==0)d[u]=0;
    return flow;
}

ll dinic(){
    ll flow = 0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        flow += dfs(s,INF);
    }
    return flow;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    s=n+1,t=n+2;
    // 1~n s=n+1,t=n+2
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        add_edge(n+1,i,x);
        add_edge(i,n+2,x^1);
    }
    for(int i=0;i<m;i++){
        int a,b;scanf("%d%d",&a,&b);
        add_edge(a,b,1);
        add_edge(b,a,1);
    }
    printf("%d\n",dinic());
    return 0;
}

二者选其一问题（2）

洛谷P1361 小M的作物

现在问题出现了一些变化：
有 $n$ 个物品，划分到两个集合 $A,B$ 中，第 $i$ 个物品划分到集合 $A$ 收益 $a_i$，划分到集合 $B$ 收益 $b_i$。有 $m$ 个组合，每个组合有 $c_j$ 个人，若组合中的全部划分在 $A$ 中，收益 $w_{aj}$，若全部划分在 $B$ 中，收益 $w_{bj}$。求最大收益。

对于最大收益，我们可以考虑转化一下问题再用最小割。然后用总边权减去最小割，得到的就是最大收益。具体来说，第 $i$ 个物品划分到集合 $A$ 损失 $b_i$，划分到集合 $B$ 损失 $a_i$。对于一个组合若全部划分在 $A$ 中，损失 $w_{bj}$，若全部划分在 $B$ 中，损失 $w_{aj}$，否则损失 $w_{aj}+w_{bj}$。这样即可求最小损失。

对于组合问题，一种很常见的思路就是将这个组合打包到一起（建立虚点）。具体来说建图方法是，在上一问建图的基础上，对每个组合增加两个虚点，两个虚点分别与 $s,t$ 连边，虚点与组合内点连边权为无穷的边。

若 ${1,2,3}$ 是一个组合，建出图如下。

我们思考一下这样的正确性。

1. 若全部划分在一个集合中

   我们把与 $s$ 划分在一起的点染成红色，与 $t$ 划分在一起的点染成蓝色。假设与 $s$ 划分在一起，则划分如下。

   

   接下来要决定的是虚点的划分。注意到不可能把边权为无穷的边割掉，所以右边的虚点一定是红色（与 $s$ 划分到一起），不然就会出现边权为无穷的边在割边集中。左边的虚点是红色还是蓝色并不会产生无穷的问题，但是我们求的是最小割，染成红色明显割容量更小。最终割边如下图绿箭头所示。

   

   我们注意到，这时候割的容量就是我们前文所提到的损失。若全部与 $t$ 划分在一起，情况类似。

2. 若划分在两个集合中
   假设 $1,2$ 染成蓝色，$3$ 染成红色。如下图。

   

   同理，这两个虚点一定一个红一个蓝，否则就会出现无穷边权的边加入割边。

   

   这时候的割容量也恰好就是我们的损失。正确性显然。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long

struct Edge{
    int u,v;
    ll f,c;
};      

const ll INF = 0x3f3f3f3f3f3f3f;
const int N = 4e3+5;
vector<Edge> edges;
vector<int> G[N];

void add_edge(int u,int v,ll w){
    edges.push_back({u,v,0,w});
    edges.push_back({v,u,0,0});
    auto cnt = edges.size();
    G[u].push_back(cnt-2);
    G[v].push_back(cnt-1);
}

int s,t;

bool vis[N];int d[N];
bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    d[s]=0;
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i=0;i<G[u].size();i++){
            auto& e = edges[G[u][i]];
            if(!vis[e.v] && e.f<e.c){
                d[e.v]=d[u]+1;
                vis[e.v]=1;
                q.push(e.v);
            }
        }
    }
    return vis[t];
}   

int cur[N];
ll dfs(int u,ll a){
    if(u==t || a==0) return a;
    ll flow = 0;
    for(int &i=cur[u];i<G[u].size();i++){
        auto& e = edges[G[u][i]];
        if(d[u]+1 == d[e.v]){
            auto f = dfs(e.v,min(a,e.c-e.f));
            e.f += f;
            edges[G[u][i]^1].f -= f;
            a -= f;
            flow += f;
            if(a==0) break;
        }
    }
    if(flow==0)d[u]=0;
    return flow;
}

ll dinic(){
    ll flow = 0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        flow += dfs(s,INF);
    }
    return flow;
}

int main(){
    int n;
    scanf("%d",&n);
    s=n+1,t=n+2;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        int a;scanf("%d",&a);
        add_edge(s,i,a);ans+=a;
    }
    for(int i=1;i<=n;i++){
        int b;scanf("%d",&b);
        add_edge(i,t,b);ans+=b;
    }
    int m;
    scanf("%d",&m);
    for(int i=0,j=t+1;i<m;i++,j+=2){
        int k;scanf("%d",&k);
        int wa,wb;scanf("%d%d",&wa,&wb);
        ans+=wa+wb;
        add_edge(s,j,wa);
        add_edge(j+1,t,wb);
        while(k--){
            int x;
            scanf("%d",&x);
            add_edge(j,x,INF);
            add_edge(x,j+1,INF);
        }
    }
    ans -= dinic();
    printf("%lld\n",ans);
    return 0;
}

最大权闭合图

洛谷P2762 太空飞行计划问题

先考虑求出最大净收益。

1. 对于每个实验，连一条从源点到实验，边权为实验利益的边。

2. 对于每个需要的仪器，连一条从实验到器材，边权为 $\infty$ 的边。

3. 对于每个仪器，连一条从器材到汇点，边权为器材耗费的边。

这样建图后用求最小割，答案即为实验利益总和 $\sum p$ 减去最小割 $c(s,t)_{\min}$

我们规定，与源点在同一个集合代表被选中。若一个实验被选中，由于有到器材且边权为无穷的边，这些器材也一定被选中。这时候割的容量增加器材的价格。（即代表花费了这些买器材的钱）

若一个实验没有被选中，割的容量增加实验的利益。（即代表实验的这些钱没有收到亏损了）

在考虑求出选择的物品集合。我们回到最小割的定义：将一张图划分为两个点集，使两个点集间连边权值和最小。选择的物品集合就是与源点在同一个点集内的点。我们可以知道，两个点集间的边的流量一定流满，所以最后在残量网络上，与源点连通点就是选择的物品。（在Dinic算法里，就是最后一次 bfs 过程中 d 数组不为 $0$）

AC代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long

struct Edge{
    int u,v;
    ll f,c;
};      

const ll INF = 0x3f3f3f3f3f3f3f;
const int N = 150;
vector<Edge> edges;
vector<int> G[N];

void add_edge(int u,int v,ll w){
    // printf("add %d %d %lld\n",u,v,w);
    edges.push_back({u,v,0,w});
    edges.push_back({v,u,0,0});
    auto cnt = edges.size();
    G[u].push_back(cnt-2);
    G[v].push_back(cnt-1);
}

int s,t;

bool vis[N];int d[N];
bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    d[s]=0;
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i=0;i<G[u].size();i++){
            auto& e = edges[G[u][i]];
            if(!vis[e.v] && e.f<e.c){
                d[e.v]=d[u]+1;
                vis[e.v]=1;
                q.push(e.v);
            }
        }
    }
    return vis[t];
}   

int cur[N];
ll dfs(int u,ll a){
    if(u==t || a==0) return a;
    ll flow = 0;
    for(int &i=cur[u];i<G[u].size();i++){
        auto& e = edges[G[u][i]];
        if(d[u]+1 == d[e.v]){
            auto f = dfs(e.v,min(a,e.c-e.f));
            e.f += f;
            edges[G[u][i]^1].f -= f;
            a -= f;
            flow += f;
            if(a==0) break;
        }
    }
    if(flow==0)d[u]=0;
    return flow;
}

ll dinic(){
    ll flow = 0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        flow += dfs(s,INF);
    }
    return flow;
}

char tools[10000];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    s=n+m+1,t=n+m+2;
    ll ans;
    for(int i=1;i<=n;i++){
        int cost;scanf("%d",&cost);
        add_edge(s,i,cost);ans+=cost;
        memset(tools,0,sizeof tools);
        cin.getline(tools,10000);
        int ulen=0,tool;
        while (sscanf(tools+ulen,"%d",&tool)==1){
            //tool是该实验所需仪器的其中一个      
            //这一行，你可以将读进来的编号进行储存、处理，如连边。
            add_edge(i,tool+n,INF);
            
            if (tool==0) ulen++;
            else {
                while (tool) {
                    tool/=10;   
                    ulen++;
                }
            }
            ulen++;
        }
    }

    for(int i=n+1;i<=n+m;i++){
        int cost;scanf("%d",&cost);
        add_edge(i,t,cost);
    }

    ans -= dinic();

    for(int i=1;i<=n;i++){
        if(vis[i])printf("%d ",i);
    }
    puts("");
    for(int i=n+1;i<=n+m;i++){
        if(vis[i])printf("%d ",i-n);
    }
    puts("");
    printf("%lld\n",ans);
    return 0;
}