DDOSvoid's Blog

网络流

发表于 更新于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

定义

  • 网络

如果一个有向带权图 $G$，满足以下条件，则称为网络流图：

  1. 仅有一个入度为 $0$ 的顶点 $s$，称 $s$ 为源点

  2. 仅有一个出度为 $0$ 的顶点 $t$，称 $t$ 为汇点

  3. 每条边的权值都是非负数，称为该边的容量，记作 $c(u,v)$

    弧的流量：通过容量网络 $G$ 中每条弧 $$ 上的流量记作 $f(u,v)$

  • 性质

任意一个时刻 $T$，图 $G$ 都要满足 $3$ 个条件

  1. 容量限制：对于任意 $u,v\in V$，$f(u,v)\le c(u,v)$
  2. 反对称性：对于任意 $u,v\in V$，$f(u,v)=-f(v,u)$
  3. 流量守恒：对于任意 $u\in V,u\neq s,u\neq t$，一定有 $\sum f(u,v)=0$
  • 残量网络

在任意时刻，网络中所有节点以及将所有边的容量改为 $c(u,v)-f(u,v)$ 的边构成的子图

如果 $c(u,v)-f(u,v)=0$ 则将这条边删掉

注意到残留网络中的 $c’(u,v)$ 可能会大于 $c(u,v)$，因为流量可以是负的

  • 增广路

一条从 $s$ 到 $t$ 的路径，且路径上所有边的剩余流量都大于 $0$

  • 割集、割

网络 $G$ 的割集 $C[S,T]$ 是将点集 $V$ 分成 $s\in S$ 且 $t\in T$ 的两部分点集之后，所有连接 $S$ 和 $T$ 的边构成的边集，注意到割集 $C[S,T]$ 并没有要求 $S$ 或者 $T$ 中点连通

网络 $G$ 的割是割集中有向边的容量和

最大流最小割定理

增广路定理

当我们已经求出一个流 $F$ 时，残留网络中不存在增广路则流 $F$ 为最大流

最大流最小割定理

  1. 任何一个流都小于等于任意一个割

    我们随便搞出来一个割集 $C[S,T]$，注意到 $C[S,T]$ 中的边的容量一定大于等于流量

    而流一定小于等于这些边的流量之和

  2. 最大流等于某一个割

    我们现在有一个最大流，根据增广路定理

    残留网络中已经不存在增广路了

    我们把 $s$ 能到的点集设为 $S$，不能到达的点集设为 $T$

    这样我们就构造出了一个割集 $C[S,T]$，注意到割集中的边一定满流，否则还能继续增广

    所以这个割等于最大流

  3. 令最大流为 $Fm$，构造出的割为 $Cm$

    那么我们已经有 $F\le Fm=Cm\le C$，也就是说这个构造出的割为最小割，且最大流等于最小割

费用流

对于一个网络 $G$，每个边除了容量和流量外，还多了一个单位费用

每条边的费用为这条边的容量乘以单位费用

模板

最大流

一般情况下，$dinic$ 的时间复杂度为 $O(n^2m)$

二分图中，$dinic$ 的时间复杂度为 $O(\sqrt nm)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct Edge {
    int to, next, w;
} e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

inline void Add_edge(int u, int v, int w) {
    add_edge(u, v, w); add_edge(v, u, 0);
}

int dep[maxn], s, t; 
bool bfs() {
    queue<int> Q; Q.push(s); 
    fill(dep, dep + maxn, 0); dep[s] = 1; 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (w > 0 && !dep[v]) {
                dep[v] = dep[u] + 1;
                Q.push(v); if (v == t) return 1;
            }
        }
    } return 0; 
}

int dfs(int u, int _w) {
    if (!_w || u == t) return _w;
    int s = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (w > 0 && dep[v] == dep[u] + 1) {
            int di = dfs(v, min(_w - s, w));
            e[i].w -= di; e[i ^ 1].w += di;
            s += di; if (s == _w) break; 
        }
    }
    if (s < _w) dep[u] = 0; 
    return s;
} 

int mf;
int dinic() {
    while (bfs()) mf += dfs(s, INF);
    return mf; 
}

最小费用最大流

spfa 每次找一条增广路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct Edge {
    int to, next, w, fi;
} e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w, int fi) {
    e[c1].to = v; e[c1].w = w; e[c1].fi = fi;
    e[c1].next = head[u]; head[u] = c1++;
}

inline void Add_edge(int u, int v, int w, int fi) {
    add_edge(u, v, w, fi); add_edge(v, u, 0, -fi);
}

bool vis[maxn]; int s, t;
int la[maxn], pre[maxn], dis[maxn];
bool spfa() {
    fill(dis, dis + maxn, INF); dis[s] = 0;
    fill(vis, vis + maxn, 0); vis[s] = 1;
    deque<int> Q; Q.push_front(s); pre[t] = -1;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop_front(); vis[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w, fi = e[i].fi;
            if (w > 0 && dis[v] > dis[u] + fi) {
                dis[v] = dis[u] + fi; pre[v] = u; la[v] = i;
                if (vis[v]) continue; vis[v] = 1;
                if (Q.empty() || dis[v] <= dis[Q.front()]) Q.push_front(v);
                else Q.push_back(v);
            }
        }
    }
    return ~pre[t];
}
 
int mf, mc;
int mcmf() {
    while (spfa()) {
        int fl = INF; 
        for (int now = t; now != s; now = pre[now]) fl = min(fl, e[la[now]].w);
        for (int now = t; now != s; now = pre[now]) e[la[now]].w -= fl, e[la[now] ^ 1].w += fl;
        mc += fl * dis[t]; mf += fl;
    } return mc;
}

在最短路图上跑 dinic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
struct Edge {
    int to, next, w, fi;
} e[maxm * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w, int fi) {
    e[c1].to = v; e[c1].w = w; e[c1].fi = fi;
    e[c1].next = head[u]; head[u] = c1++;
}

inline void Add_edge(int u, int v, int w, int fi) {
    add_edge(u, v, w, fi); add_edge(v, u, 0, -fi);
}

bool vis[maxn]; int dis[maxn], s, t;
bool spfa() {
    queue<int> Q; Q.push(s);
    fill(vis, vis + maxn, 0); vis[s] = 1;
    fill(dis, dis + maxn, INF); dis[s] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = 0; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w, fi = e[i].fi;
            if (w > 0 && dis[v] > dis[u] + fi) {
                dis[v] = dis[u] + fi;
                if (vis[v]) continue; vis[v] = 1; Q.push(v);
            }
        }
    } return dis[t] != INF;
}

bool ins[maxn]; int mf, mc;
int dfs(int u, int _w) {
    if (!_w || u == t) return _w;
    int s = 0; ins[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w, fi = e[i].fi;
        if (!ins[v] && w > 0 && dis[v] == dis[u] + fi) {
            int di = dfs(v, min(_w - s, w));
            e[i].w -= di; e[i ^ 1].w += di;
            s += di; mc += di * fi; if (s == _w) break;
        }
    }
    if (s < _w) dis[u] = INF; 
    ins[u] = 0; return s;
} 

void mcmf() {
    mf = mc = 0; 
    while (spfa()) mf += dfs(s, INF); 
}