前言

网络流真神奇

最大流最小割

参考 (opens new window)

最大流的流量=最小割的容量

割的容量：对于割$$(S, T)$$，割的容量$C(S, T)=\sum c(u, v) (u \in S、v \in T、<u,v> \in E)$，也就是说，割的容量等于$S$中所有点到$T$中所有点的前向弧的容量之和。容量最小的割被称为最小割。

也就是说，对于$S=\{S, B\}, T=\{A, T\}$，割$=\{(S, A),(B, T),(A,B)\}$，割的容量$=w(S, A)+w(B,T)$

最小割

BZOJ 3894 (opens new window) 文理分科

见[AC代码](#BZOJ 3894 AC代码)

最大权闭合图

对于有向图$G=(V,E)$，特殊子集$V' \in V$有以下性质：若$(u,v) \in E$且$u \in V'$，则$v \in V'$。每个点有点权$w_v,w_v\in R$。求一个点权和最大的特殊子集$V'$，即最大化$\sum_{v\in V'}w_v$

图的构造如下：

对原图中的有向边$(u,v)\in E$，建一条容量为$+\infty$的边$(u,v)$

从源点$s$向所有点权为正的点建边$(s,u)$，容量为$w_u$

从所有点权为负的点向汇点$t$建边$(v,t)$，容量为$-w_v$

定义$+\infty>\sum \mid w_v\mid$

求得最小割为$c[S,T]$，那么答案为$\sum_{v\in V^+}w_v-c[S,T]$，其中$V^+$为所有正权点组成的集合。

最大利益=所有点正权值之和-最小割

以割为界，靠近$s$一侧的点属于最大权闭合图的点

具体证明见《最小割模型在信息学竞赛中的应用》 (opens new window)3.2

例题 POJ 2987

[AC代码](#POJ 2987 AC代码)

附录

BZOJ 3894 AC代码

// 头文件等略去
#define ll long long

using namespace std;

const ll inf = 0x3f3f3f3f;
struct Dinic{
    const static int mx_edge = 3e6 + 100, mx_node = 3e4 + 100;
    int head[mx_node], deep[mx_node], edge_cnt, n;
    int cur[mx_node];
    struct E{int v, next; ll cap;} edge[2 * mx_edge];
    void init(int nx){
        n = nx; edge_cnt = 0;
        for(int i=0; i<=n; i++) head[i] = -1;
    }
    void add_edge(int u, int v, ll cap){
        edge[edge_cnt] = {v, head[u], cap}; head[u] = edge_cnt++;
        edge[edge_cnt] = {u, head[v], 0}; head[v] = edge_cnt++;
    }
    bool bfs(int s, int t){
        for(int i=0; i<=n; i++) deep[i] = -1;
        deep[s] = 0;
        queue<int> que; que.push(s);
        while(!que.empty()){
            int u = que.front(); que.pop();
            for(int i=head[u]; ~i; i=edge[i].next){
                if(edge[i].cap){
                    int v = edge[i].v;
                    if(deep[v]==-1) deep[v] = deep[u]+1, que.push(v);
                }
            }
        }
        return deep[t] != -1;
    }

    ll dfs(int t, int u, ll limit){
        if(u==t||!limit) return limit;
        ll ret = 0;
        for(int &i=cur[u]; ~i; i=edge[i].next){
            int v = edge[i].v;
            if(deep[v] == deep[u] + 1){
                ll df = dfs(t, v, min(limit, edge[i].cap));
                edge[i].cap -= df;
                edge[i^1].cap += df;
                ret += df;
                limit -= df;
                if(!limit) return ret;
            }
        }
        return ret;
    }

    ll dinic(int s, int t){
        ll ret = 0;
        while(bfs(s, t)){
            for(int i=0; i<=n; i++) cur[i] = head[i];
            ret += dfs(t, s, inf);
        }

        return ret;
    }

} dinic; // dinic模板

const int dx[]={0,0,0,1,-1};
const int dy[]={0,1,-1,0,0};
int n, m;

bool is_legal(int r, int c){return !(r < 0 || c < 0 || r >= n || c >= m);}

int index(int r, int c, int num){return r * m + c + (num * n * m);} // 这里害我debug好久

void solve(){
    cin >> n >> m;
    dinic.init(3 * n * m + 10);
    int s = 3 * n * m + 1, t = 3 * n * m + 2;
    ll sum = 0;
    for(int r=0, w; r<n; r++){
        for(int c=0; c<m; c++){
            cin >> w;
            sum += w;
            dinic.add_edge(s, index(r, c, 0), w);
        }
    }
    for(int r=0, w; r<n; r++){
        for(int c=0; c<m; c++){
            cin >> w;
            sum += w;
            dinic.add_edge(index(r, c, 0), t, w);
        }
    }
    for(int r=0, w; r<n; r++){
        for(int c=0; c<m; c++){
            cin >> w;
            sum += w;
            dinic.add_edge(s, index(r, c, 1), w);
            for(int k=0, nr, nc; k<5; k++){
                nr = r + dx[k], nc = c + dy[k];
                if(is_legal(nr, nc)){
                    dinic.add_edge(index(r, c, 1), index(nr, nc, 0), inf);
                }
            }
        }
    }
    for(int r=0, w; r<n; r++){
        for(int c=0; c<m; c++){
            cin >> w;
            sum += w;
            dinic.add_edge(index(r, c, 2), t, w);
            for(int k=0, nr, nc; k<5; k++){
                nr = r + dx[k], nc = c + dy[k];
                if(is_legal(nr, nc)){
                    dinic.add_edge(index(nr, nc, 0), index(r, c, 2), inf);
                }
            }
        }
    }
    cout << sum - dinic.dinic(s, t) << endl;
}

int main(){
    solve();
}

POJ 2987 AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define ll long long

using namespace std;

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5e3 + 1000;

struct Dinic{
	// 略去
} dinic; // dinic模板

bool vis[maxn];

void dfs(int u){
    vis[u] = true;
    for(int i=dinic.head[u], v; ~i; i=dinic.edge[i].next){
        if(dinic.edge[i].cap == 0) continue;
        v = dinic.edge[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
}

int n, m;
ll weight[maxn];
signed main() {
    ll sum = 0;
    cin >> n >> m;
    dinic.init(n + 7);
    for(int i=1; i<=n; i++) {
        cin >> weight[i];
        if(weight[i] > 0) sum += weight[i];
    }
    for(int i=0, u, v; i<m; i++){
        cin >> u >> v;
        dinic.add_edge(u, v, inf);
    }
    for(int i=1; i<=n; i++){
        if(weight[i] > 0) dinic.add_edge(n+1, i, weight[i]);
        if(weight[i] < 0) dinic.add_edge(i, n+2, -weight[i]);
    }
    ll min_flow = dinic.dinic(n+1, n+2);
    int cnt = 0;
    dfs(n+1);
    for(int i=1; i<=n; i++) cnt += vis[i];
    cout << cnt << " " << sum - min_flow << endl;
}