发表更新C++算法7 分钟读完 (大约1049个字)0次访问

Cpp算法-网络流相关

网络流算法相关模板,讲解__以后再说吧__,咕咕咕

注:本文使用vector建图

网络最大流

Edmonds-Karp算法

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
int n, m, s, t, ans;

struct Edge {
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f){}
};

vector<Edge> edges;
vector<int> G[maxn];
int a[maxn], p[maxn];

void add(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    int mm = edges.size();
    G[from].push_back(mm - 2);
    G[to].push_back(mm - 1);
}

void EdmondsKarp() {
    ans = 0;
    for (;;) {
        memset(a, 0, sizeof(a));
        queue<int> Q;
        Q.push(s);
        a[s] = 0x3f3f3f3f;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = 0; i < G[x].size(); ++i) {
                Edge& e = edges[G[x][i]];
                if (!a[e.to] && e.cap > e.flow) {
                    p[e.to] = G[x][i];
                    a[e.to] = min(a[x], e.cap - e.flow);
                    Q.push(e.to);
                }
            }
            if (a[t]) break;
        }
        if (!a[t]) break;
        for (int u = t; u != s; u = edges[p[u]].from) {
            edges[p[u]].flow += a[t];
            edges[p[u] ^ 1].flow -= a[t];
        }
        ans += a[t];
    }
    return;
}

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
const int maxn = 10010;

int n, m, s, t, d[maxn], cur[maxn];
struct Edge {
    int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn];
void add(int from, int to, int cap) {
    edges.push_back((Edge) {from, to, cap, 0});
    edges.push_back((Edge) {to, from, 0, 0});
    int mm = edges.size();
    G[from].push_back(mm - 2);
    G[to].push_back(mm - 1);
}

bool vis[maxn];

bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (int i = 0; i < G[x].size(); ++i) {
            Edge& e = edges[G[x][i]];
            if (!vis[e.to] && e.cap > e.flow) {
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                Q.push(e.to);
            }
        }
    }
    return vis[t];
}

int DFS(int x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f;
    for (int& i = cur[x]; i < G[x].size(); ++i) {
        Edge& e = edges[G[x][i]];
        if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
            e.flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
            if (a == 0) break;
        }
    }
    return flow;
}

int MaxFlow(int s, int t) {
    int flow = 0;
    while (BFS()) {
        memset(cur, 0, sizeof(cur));
        flow += DFS(s, 0x3f3f3f3f);
    }
    return flow;
}

ISAP算法

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
const int maxn = 10010;
const int inf  = 0x3f3f3f3f;

int n, m, s, t;
int d[maxn], p[maxn], num[maxn], cur[maxn];
bool vis[maxn];

struct Edge {
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f){}
};
vector<Edge> edges;
vector<int> G[maxn];
void add(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    int mm = edges.size();
    G[from].push_back(mm - 2);
    G[to].push_back(mm - 1);
}

void bfs() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(t);
    d[t] = 0; vis[t] = 1;
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (int i = 0; i < G[x].size(); ++i) {
            Edge& e = edges[G[x][i]];
            if (!vis[e.from] && e.cap > e.flow) {
                vis[e.from] = 1;
                d[e.from] = d[x] + 1;
                Q.push(e.from);
            }
        }
    }
}

int Augment() {
    int x = t, a = inf;
    while (x != s) {
        Edge& e = edges[p[x]];
        a = min(a, e.cap - e.flow);
        x = edges[p[x]].from;
    }
    x = t;
    while (x != s) {
        edges[p[x]].flow += a;
        edges[p[x] ^ 1].flow -= a;
        x = edges[p[x]].from;
    }
    return a;
}

int ISAP(int s, int t) {
    int flow = 0;
    bfs();
    memset(num, 0, sizeof(num));
    for (int i = 0; i < n; ++i) num[d[i]]++;
    int x = s;
    memset(cur, 0, sizeof(cur));
    while (d[s] < n) {
        if (x == t) {
            flow += Augment();
            x = s;
        }
        int ok = 0;
        for (int i = cur[x]; i < G[x].size(); ++i) {
            Edge& e = edges[G[x][i]];
            if (e.cap > e.flow && d[x] == d[e.to] + 1) {
                ok = 1;
                p[e.to] = G[x][i];
                cur[x] = i;
                x = e.to;
                break;
            }
        }
        if (!ok) {
            int mm = n - 1;
            for (int i = 0; i < G[x].size(); ++i) {
                Edge& e = edges[G[x][i]];
                if (e.cap > e.flow) mm = min(mm, d[e.to]);
            }
            if (--num[d[x]] == 0) break;
            num[d[x] = mm + 1]++;
            cur[x] = 0;
            if (x != s) x = edges[p[x]].from;
        }
    }
    return flow;
}

最小费用最大流

Bellman-Ford算法

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
const int maxn = 10010;
const int inf  = 0x3f3f3f3f;

int n, m, s, t, ansflow;
int vis[maxn], d[maxn], p[maxn], a[maxn];
long long anscost;

struct Edge {
    int from, to, cap, flow, cost;
    Edge(int u, int v, int c, int f, int w): from(u), to(v), cap(c), flow(f), cost(w){}
};
vector<Edge> edges;
vector<int> G[maxn];
void add(int u, int v, int c, int w) {
    edges.push_back(Edge(u, v, c, 0, w));
    edges.push_back(Edge(v, u, 0, 0,-w));
    int mm = edges.size();
    G[u].push_back(mm - 2);
    G[v].push_back(mm - 1);
}

bool BellmanFord(int& flow, long long& cost) {
    for (int i = 1; i <= n; ++i) d[i] = inf;
    memset(vis, 0, sizeof(vis));
    d[s] = 0; vis[s] = 1; p[s] = 0; a[s] = inf;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        vis[x] = 0;
        for (int i = 0; i < G[x].size(); ++i) {
            Edge& e = edges[G[x][i]];
            if (e.cap > e.flow && d[e.to] > d[x] + e.cost) {
                d[e.to] = d[x] + e.cost;
                p[e.to] = G[x][i];
                a[e.to] = min(a[x], e.cap - e.flow);
                if (!vis[e.to]) {
                    Q.push(e.to);
                    vis[e.to] = 1;
                }
            }
        }
    }
    if (d[t] == inf) return false;
    flow += a[t];
    cost += (long long)d[t] * (long long)a[t];
    for (int u = t; u != s; u = edges[p[u]].from) {
        edges[p[u]].flow += a[t];
        edges[p[u] ^ 1].flow -= a[t];
    }
    return true;
}

int MinCostMaxFlow(long long& cost) {
    int flow = 0; cost = 0;
    while (BellmanFord(flow, cost));
    return flow;
}

Cpp算法-网络流相关

https://blog.tonycrane.cc/p/c3cdab79.html

作者

TonyCrane

发布于

2019-04-30

更新于

2020-05-05

许可协议

#
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
图论2
学习1
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记29
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

目录

×