网络流：最小割
发表算法 / 网络流18 分钟读完 (大约2681个字)

网络流：最小割

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

S - T 最小割

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

阅读更多
网络流：最大流
发表算法 / 网络流8 分钟读完 (大约1169个字)

网络流：最大流

EK

增广路方法是很多网络流算法的基础。其思路是每次找出一条从源到汇的能够增加流的路径，调整流值和残留网络 ，直到没有增广路为止。

EK 算法就是不断的找最短路，找的方法就是每次找一条边数最少的增广（即最短路径增广）。

最多要增广多少次？

可以证明，最多 O(VE)​ 次增广，可以达到最大流。

如何找到一条增广路？

先明确什么是增广路。增广路是一条从s到t的路径，路径上每条边残留容量都为正。把残留容量为正的边设为可行的边，那么我们就可以用简单的 BFS 得到边数最少的增广路。

阅读更多
网络流：模板
发表算法 / 网络流12 分钟读完 (大约1863个字)

网络流：模板

P3376 网络最大流（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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 11000, M = 110000;
const int INF = 0x7fffffff;
struct node {
    int u, v, w, next;
} e[M << 1];
int cur[N], h[N], tot;
int dfn[N], ans, n, m, s, t;
void add(int u, int v, int w) {
    e[tot] = node({u, v, w, h[u]});
    cur[u] = h[u] = tot++;
}

bool bfs() {
    memset(dfn, 0, sizeof dfn);
    queue<int> q;
    dfn[s] = 1;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and !dfn[v]) {
                dfn[v] = dfn[u] + 1;
                q.push(v);
                if(v == t) return true;
            }
        }
    }
    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) {
        int v = e[i].v;
        cur[u] = i;
        if(e[i].w and dfn[v] == dfn[u] + 1) {
            int f = dfs(v, min(w, e[i].w));
            e[i].w -= f; e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}
void dinic() {
    while(bfs()) {
        memcpy(cur, h, sizeof cur);
        ans += dfs(s, INF);
    }
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(h, -1, sizeof h);
    for(int i=1, u, v, w; i<=m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, 0);
    }
    dinic();
    printf("%d\n", ans);
    return 0;
}

P3381 最小费用最大流（单路增广）

Dijkstra

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline

const int N = 5500, M = 55000, INF = 0x3f3f3f3f;

struct point {
    int u, val;
    point(int _u = 0, int _val = 0): u(_u), val(_val) {}
    bool operator < (const point &o) const { return val > o.val; } 
};

priority_queue <point> q;

struct node {
    int u, v, w, f, next;
    node() {}
} e[M << 1];
int head[N], tot = 0;

il void add(int u, int v, int w, int f) {
    e[tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].f = f;
    e[tot].next = head[u]; head[u] = tot++;
}

int h[N], dis[N], flow[N], pre[N];

int n, m, s, t;

int maxflow = 0, mincost = 0;
il bool dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    memset(pre, -1, sizeof pre);
    
    dis[s] = 0;
    q.push(point(s, 0));
    while (!q.empty()) {
        int u = q.top().u, val = q.top().val;
        q.pop();
        if (val > dis[u]) continue;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w and dis[v] > dis[u] + e[i].f + h[u] - h[v]) {
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                dis[v] = dis[u] + e[i].f + h[u] - h[v];
                q.push(point(v, dis[v]));
            }
        }
    }
    return dis[t] != INF;
}

il void check() {
    
    for (int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    maxflow += flow[t];
    mincost += (dis[t] - h[s] + h[t]) * flow[t];
    
    for(int i=1; i<=n; ++i) h[i] += dis[i];
}


int main() {
    
    memset(head, -1, sizeof head);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while (dijkstra()) check();
    printf("%d %d\n", maxflow, mincost);
    
    return 0;
}

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 5500, M = 110000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, f, next;
} e[M];
int h[N], tot = 0;

void add(int u, int v, int w, int f) {
    e[tot] = {u, v, w, f, h[u]};
    h[u] = tot++;
}

int pre[N], flow[N], dis[N];
bool vis[N];

int n, m, s, t, maxflow, mincost;

bool spfa() {
    
    memset(pre, -1, sizeof pre);
    memset(vis, false, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    
    queue<int> q;
    q.push(s);
    vis[s] = true;
    dis[s] = 0;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and dis[v] > dis[u] + e[i].f) {
                dis[v] = dis[u] + e[i].f;
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                if(!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    
    return dis[t] != INF;
}

void check() {
    for(int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    
    mincost += dis[t] * flow[t];
    maxflow += flow[t];
}
int main() {
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    memset(h, -1, sizeof h); 
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while(spfa()) check();
    
    printf("%d %d\n", maxflow, mincost);

    return 0;
}

LOJ115 无源汇有上下界可行流（超级源汇）

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline

const int N = 220, M = 11000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, next;
} e[M * 6];

int head[N], cur[N], tot = 0;

il void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
}

int h[N], n, m, ss, tt;
il bool bfs() { //分层 
    
    memset(h, 0, sizeof h);
    memcpy(cur, head, sizeof cur);
    queue<int> q;
    q.push(ss);
    h[ss] = 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]) {
                h[v] = h[u] + 1;
                if(v == tt) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int u, int low) {
    if(u == tt) 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));
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}

int tflow = 0, sflow = 0;
il void dinic() {
    
    for(int i = head[ss]; i != -1; i = e[i].next)
        sflow += e[i].w; //出流量 
        
    while(bfs()) dfs(ss, INF);
    
    for(int i = head[tt]; i != -1; i = e[i].next) 
        tflow += e[i].w; //入流量 
    
    if(sflow == tflow) { //满流 
        printf("YES\n");
        for(int i=0; i<tot; i+=6) 
            printf("%d\n", e[i+1].w + e[i+5].w); //反边流量和 
    } else printf("NO\n");
    
}
int main() {
    
    freopen("loj115.in", "r", stdin);
    
    scanf("%d%d", &n, &m);
    
    memset(head, -1, sizeof head);
    ss = 0, tt = n+1;
    for(int i=1, u, v, l, h; i<=m; ++i) { //建图 
        scanf("%d%d%d%d", &u, &v, &l, &h);
        add(u, tt, l);
        add(tt, u, 0);
        add(ss, v, l);
        add(v, ss, 0);
        add(u, v, h-l);
        add(v, u, 0);
    }
    
    dinic();
    
    return 0;
}

有源汇有上下界（转无源汇，然后断边）

最大流（顺流增广）

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 220, M = 22000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
    e[tot] = (node) {v, u, 0, head[v]};
    head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {
    
    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], v; i != -1; i = e[i].next) {
            v = e[i].v;
            if(e[i].w and !h[v]) {
                h[v] = h[u] + 1;
                if(v == t) return true;
                q.push(v); 
            }
        }
    }
    return false;
}

int dfs(int u, int low, int t) {
    if(u == t) return low;
    
    int w = low;
    for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
        v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w), t);
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}

int main() {
    
    //freopen("loj116.in", "r", stdin);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    ss = 0, tt = n+1;
    memset(head, -1, sizeof head);
    for(int i=1, u, v, l, h; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &l, &h);
        in[u] -= l; in[v] += l;
        add(u, v, h-l);
    }
    
    for(int i=1; i<=n; ++i) {
        if(!in[i]);
        else if(in[i] > 0) {
            sflow += in[i];
            add(ss, i, in[i]);
        } else {
            add(i, tt, -in[i]);
        }
    }
    
    add(t, s, INF);
    
    while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);
    
    if(sflow != tflow) {
        printf("please go home to sleep\n");
        return 0;
    }
    
    for(int i = head[ss]; i != -1; i = e[i].next) 
        e[i].w = e[i^1].w = 0;
    
    for(int i = head[tt]; i != -1; i = e[i].next)
        e[i].w = e[i^1].w = 0;
    
    int sum = e[--tot].w;
    e[tot-1].w = e[tot].w = 0;
    
    while(bfs(s, t)) sum += dfs(s, INF, t);
    
    printf("%d\n", sum);
        
    return 0;
}

最小流（逆流增广）

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 220, M = 22000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
    e[tot] = (node) {v, u, 0, head[v]};
    head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {
    
    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], v; i != -1; i = e[i].next) {
            v = e[i].v;
            if(e[i].w and !h[v]) {
                h[v] = h[u] + 1;
                if(v == t) return true;
                q.push(v); 
            }
        }
    }
    return false;
}

int dfs(int u, int low, int t) {
    if(u == t) return low;
    
    int w = low;
    for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
        v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w), t);
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}

int main() {
    
    //freopen("loj116.in", "r", stdin);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    ss = 0, tt = n+1;
    memset(head, -1, sizeof head);
    for(int i=1, u, v, l, h; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &l, &h);
        in[u] -= l; in[v] += l;
        add(u, v, h-l);
    }
    
    for(int i=1; i<=n; ++i) {
        if(!in[i]);
        else if(in[i] > 0) {
            sflow += in[i];
            add(ss, i, in[i]);
        } else {
            add(i, tt, -in[i]);
        }
    }
    
    add(t, s, INF);
    
    while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);
    
    if(sflow != tflow) {
        printf("please go home to sleep\n");
        return 0;
    }
    
    for(int i = head[ss]; i != -1; i = e[i].next) 
        e[i].w = e[i^1].w = 0;
    
    for(int i = head[tt]; i != -1; i = e[i].next)
        e[i].w = e[i^1].w = 0;
    
    int sum = e[--tot].w;
    e[tot-1].w = e[tot].w = 0;
    
    while(bfs(s, t)) sum += dfs(s, INF, t);
    
    printf("%d\n", sum);
        
    return 0;
}
网络流：消圈算法
发表算法 / 网络流9 分钟读完 (大约1278个字)

网络流：消圈算法

注：下文中的权均表示费用。

消圈定理

在某个流 $f$ 中，如果其残余网络中没有负圈（剩余流量为 $0$ 的边视为不存在），那它一定是当前流量下的最小费用，否则一定不是。

阅读更多
网络流：Dijkstra 求费用流
发表算法 / 网络流5 分钟读完 (大约737个字)

网络流：Dijkstra 求费用流

注：下文中的边权 $w$ 均表示费用 $f$。

Dijkstra 不能求有负权边的最短路，所以我们可以对网络 $G$ 中的每一个点设置一个势函数 $h(u)$，以满足在与原图等价的新图中的边权非负。

阅读更多
关注我

分类

标签

AI2
Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Hexo2
LCA1
PB_DS1
SSH1
STL2
二分图2
动态规划3
匹配2
单调队列2
博客2
双指针1
图书馆4
图论4
小说7
尺取法1
平衡树1
排序2
数学1
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法25
网络流5
记忆化搜索4
部署1
随感2
随笔1

最新文章

归档

×