首页 算法 网络流

# 网络流：最小割

将图 GG 分为 AA 和 BB 两个点集，AA 和 BB 之间的边的集合称为无向图的割集。带权图的割 (Cut) 就是割集中的边权之和。

# S - T 最小割

特别地，对于一个网络，在满足 源点s∈点集{S},汇点t∈点集{T}(S∩T=∅)源点 s \in 点集\{S\}, 汇点 t \in 点集\{T\}(S\cap T= \varnothing) 的情况下，从 S 到 T 的边的权值和被称为 S 到 T 的割。

img

通俗地说，如果把你家和自来水厂之间的水管网络砍断了一些，那么自来水厂无论怎么放水，水都无法到达你们家，自然就停水了，砍掉的水管就是割。

砍水管的人自然希望花的力气越小越好。在所有割中，权值和最小的称为最小割。对于一个给定的 S - T 网络，如何求出它的最小割呢？

# 最大流最小割定理

网络的最大流等于最小割。

这个定理看起来很简单，但是真去思考的话其实挺麻烦的。

# 证明 Step 1：任意一个流都小于等于任意一个割

自来水公司随便给你家通点水，构成一个流，随便砍几刀砍出一个割，那么由于容量限制，每一根的被砍的水管子流出的水流量都小于管子的容量。每一根被砍的水管的水本来都要到你家的，现在流到外面，加起来得到的流量还是等于原来的流。而管子的容量加起来就是割，所以流小于等于割。

由于上面的流和割都是任意构造的，所以任意一个流小于任意一个割，即

∀F⩽∀C\forall F \leqslant \forall C

# Step 2：构造出一个流，使它等于一个割

当达到最大流时，根据增广路定理，残留网络中 s 到 t 已经没有通路了。因此，若把残余网络中 s 能到的的点的集合设为 S，不能到的点集为 T ，构造出一个割集 C[点集S,点集T]C[点集S,点集T]，所有由 S 发往 T 的边必然满流。并且，这些满流边的流量和就是当前的流，即最大流。把这些满流边作为割，就构造出了一个和最大流相等的割。

# Step 3：最大流等于最小割

设上一步构造出流和割分别为 FmF_m 和 CmC_m。

又 ∀F⩽∀C\forall F \leqslant \forall C

∴∀F⩽Fm=Cm⩽∀C\therefore \forall F \leqslant F_m=C_m \leqslant \forall C。

# 网络流等价定理

综合最大流最小割定理和增广路定理，可以得到这样的结论：

对于一个网络流图 G=(V,E)G=(V,E)，其中有源点 ss 和汇点 tt ，那么下面三个条件是等价的：

  1. 流 ff 是图 GG 的最大流；

  2. 残留网络 GG 不存在增广路；

  3. 在 GG 中必存在一个割 C[S,T]C[S,T]，使得 f=C[S,T]f=C[S,T]。

读者自证不难

# 证明 1 => 2（即增广路定理）

利用反证法，假设流 ff 是图 GG 的最大流，但是残留网络中还存在有增广路 pp，其流量为 fpf_p，则有流 f′=f+fp>ff'=f+f_p>f。这与 ff 是最大流产生矛盾。

# 证明 2 => 3（即最大流最小割定理）

总结一下上面的证明。

假设残留网络 GfG_f 不存在增广路，所以在残留网络 GfG_f 中不存在路径从 ss 到达 tt。我们定义 SS 集合为当前残留网络中 ss 能够到达的点，同时定义 T=V−ST=V-S，此时构成一个割 C(S,T)C(S,T)。

且 u∈S,v∈Tu∈S,v∈T，有 f(u,v)=c(u,v)f(u,v)=c(u,v)。若 f(u,v)<c(u,v)f(u,v)<c(u,v)，则有 Gf(u,v)>0G_f(u,v)>0，ss 可以到达 vv，与 v∈Tv \in T 矛盾。

因此有 f(S,T)=∑f(u,v)=∑c(u,v)=C(S,T)f(S,T)= \sum f(u,v)=\sum c(u,v)=C(S,T)。

# 证明 3 => 1：

由于 ff 的上界为最小割，当 ff 到达割的容量时，显然就已经到达最大值，因此 ff 为最大流。

这样就说明了为什么找不到增广路时，所求得的一定是最大流。

# 最大权闭合子图

在一个图中，我们选取一些点构成集合，记为 V，且集合中的出边（即集合中的点的向外连出的弧），所指向的终点也在 V 中，则我们称 V 为闭合图。在所有闭合图中，集合中点的权值之和最大的 V，称为最大权闭合子图。

# 栗子

img

上图中最大权闭合子图为 {3,4,5}。

# 最大权闭合子图权值和

# 构图

构建一个超级源点 s，一个超级汇点 t，所有的点按权值的正负连接到 s 和 t 上，转换成一个边权值有向图，如下图：

img

（注：点权为 0 的点可以忽略，对结果没有影响）

# 前置知识

  • 该带边权有向图的 S - T 最小割，割集中所有的边，都与 s 或 t 相连接。

显然，因为不与 s,t 相连的边，权值都是 INF，最小割不可能割在 INF 的边上。

  • 该图中的每一个简单割产生的两个子图，我们记含有点 s 的是图 S，含有点 t 的是图 T，则图 S 是最大权闭合子图。

简单割内不包含边权为 INF 的边，即不含有连通两个图的边（除了连接在 t 点上的边之外）；即，图 S 中没有边与图 T 连通，那么，所有的边都只能连接在图 S 之内，即为闭合图。

记割集中，所有连接在 s 上的边的权值和为 x1x_1，所有连接在 t 上的边的权值和为 x2x_2，则割集中所有边权值和为 x=x1+x2x=x_1+x_2。

记图 S 中所有点的权值和为 ww，记其中正权值之和为 w1w_1，负权值之和为 −w2- w_2，故 w=w1−w2w = w_1 - w_2。

因此，

w+x=w1−w2+x1−x2w+x=w_1-w_2+x_1-x_2

又，

x2=w2x_2 = w_2

因为图 S 中所有负权值的点必然连接到 t 点，而图 S 必然要与 t 分割开，故割集中，连接在 t 点上的边权值和就是图 S 中所有负权值点的权值之和取负。因而，

w+x=w1+x1w+x=w_1+x_1

显然，w1+x1w_1 + x_1 是整个图中所有正权值之和，记为 sumsum，则

w=sum−xw=sum-x

即，图 S 中所有点的权值和 = 整个图中所有正权值之和 - 割集中所有边权值和。因为 sumsum 为定值，只要我们取最小割，则图 S 中所有点的权值和就是最大的，即此时图 S 为最大权闭合子图。

# 栗子

img　　　　　img

# 解法

  • 先记录整个图中，所有正点权值的和；

  • 建立对应流网络，求最大流，最大流在数值上等于最小割，故我们得到了流网络的 s-t 最小割；

  • 所有正点权值的和减去 s-t 最小割，即得最大权闭合子图的权值和。

# P2762 太空飞行计划问题

# Hint

这里大概讲一下转换成最大流以后怎么输出。

一个结论就是假如我们跑的是 Dinic 那么我们最后一次网络流（这一次网络流并没有起任何作用，只是确认了无更多残余流量可以退出了）中，所有被分到层的都一定被选上了。

没有更多残余流量其实意味着这个图已经被割成了两部分，一个实验如果有层数意味着它没有被割掉（被选上了），一个仪器如果有层数意味着它已经被割掉了（也是被选上了）。

于是只要在最后输出所有有层数的点就行了。

# Code

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
char tools[10000];
class node {
    public:
        int u, v, w, next;
} e[N * N];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
    e[tot] = {u, v, w, head[u]};
    head[u] = tot++;
    e[tot] = {v, u, 0, head[v]};
    head[v] = tot++;
}
int h[N], n, m, s, t;
bool bfs() {
    
    memset(h, 0, sizeof h);
    memcpy(cur, head, sizeof cur);
    
    queue<int> q;
    q.push(s);
    h[s] = 1;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and h[v] == 0) {
                h[v] = h[u] + 1;
                if(v == t) return true;
                q.push(v);
            }
        }
    }
    
    return false;
}
int dfs(int u, int low) {
    if(u == t) return low;
    int w = low;
    for(int i = cur[u]; i != -1; i = e[i].next, cur[u] = i) {
        int v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w));
            if(f == 0) h[v] = 0;
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(w == 0) break;
        }
    }
    return low - w;
}
int maxflow = 0, sum = 0;
void dinic() {
    int flow;
    while(bfs()) while(flow = dfs(s, INF)) maxflow += flow;
}
int main() {
    
    //freopen("shut2.in", "r", stdin);
    
    scanf("%d%d", &m, &n);
    
    memset(head, -1, sizeof head);
    s = 0, t = n+m+1;
    for(int i=1, w; i<=m; ++i) {
        
        scanf("%d", &w);
        add(s, i, w);
        sum += w;
        
        memset(tools, '\0', sizeof tools); 
        cin.getline(tools, 10000);
        int ulen = 0, tool;
        while(sscanf(tools + ulen, "%d", &tool) == 1) {
            add(i, tool + m, INF);
            if(tool == 0) ulen++;
            else {
                while(tool) {
                    tool /= 10;
                    ulen++;
                }
            }
            ulen++;
        }
    }
    
    for(int i=1, w; i<=n; ++i) {
        scanf("%d", &w);
        add(i+m, t, w);
    }
    
    dinic();
    
    for(int i=1; i<=m; ++i) if(h[i]) printf("%d ", i);
    printf("\n");
    for(int i=1; i<=n; ++i) if(h[i+m]) printf("%d ", i);
    printf("\n");
    
    printf("%d\n", sum - maxflow);
    
    return 0;
}
# 全局最小割
可参考这篇文章。
# Code (POJ 2914, 未优化版)
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 550;
int g[N][N];
int dis[N];
bool flag[N], vis[N];
int n, m, s, t;
int main() {
    
    while(scanf("%d%d", &n, &m) != EOF) {
        
        memset(g, 0, sizeof g);
        
        for(int i=1, a, b, c; i<=m; ++i) {
            scanf("%d%d%d", &a, &b, &c);
            ++a, ++b;
            g[a][b] += c; g[b][a] += c; 
        }
        
        int ans = 0x3f3f3f3f;
        memset(flag, false, sizeof flag);
        
        for(int o=1; o<n; ++o) {
            
            s = t = 0;
            
            memset(vis, false, sizeof vis);
            memset(dis, 0, sizeof dis); 
            
            for(int p=1; p<=n; ++p) {
                
                int v = -1;
                for(int i=1; i<=n; ++i) 
                    if(!flag[i] and !vis[i] and (v == -1 or dis[v] < dis[i]))
                        v = i;
                if(v == -1) break;
                
                vis[v] = true;
                
                s=t, t=v;
                for(int i=1; i<=n; ++i) 
                    if(!flag[i] and !vis[i]) 
                        dis[i] += g[t][i];
            }
            
            flag[t] = true;
            ans = min(ans, dis[t]);
            
            if(ans == 0) break;
            
            for(int i=1; i<=n; ++i) {
                if(flag[i]) continue;
                g[s][i] += g[t][i];
                g[i][s] += g[i][t];
            }
                
        }
        
        printf("%d\n", ans);
    } 
    
    return 0;
}
  
 更新于