浅念づ昔夜's Blog

Like author, like book.

0%

网络流模板

发表于 分类于
本文字数： 627 阅读时长 ≈ 2 分钟

网络流代码合集

最大流

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
#include <bits/stdc++.h>
#define rei register int
#define maxn 100005
#define maxm 200005
using namespace std;
typedef long long ll;

struct edge {ll nxt, v, w;} e[maxm];

ll n, m, s, t, head[maxn], cnt = 1, dep[maxn], cur[maxn];

template <typename T> inline void read(T &x)
{
    x = 0; ll f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    x *= f;
}

inline void add_edge(ll u, ll v, ll w)
{
    e[++cnt].nxt = head[u];
    head[u] = cnt;
    e[cnt].v = v;
    e[cnt].w = w;
}

inline bool Bfs()
{
    queue<ll> Q;
    memset(dep, 0, sizeof(dep));
    dep[s] = 1;
    Q.push(s);
    while (Q.size())
    {
        ll u = Q.front(); Q.pop();
        cur[u] = head[u];
        for (rei i = head[u]; i; i = e[i].nxt)
        {
            ll v = e[i].v;
            if (!dep[v] && e[i].w)
            {
                dep[v] = dep[u] + 1;
                Q.push(v);
            }
        }
    }
    return dep[t] != 0; 
}

inline ll Dfs(ll u, ll flow)
{
    if (u == t) return flow;
    ll rest = flow;
    for (rei i = cur[u]; i; i = e[i].nxt)
    {
        ll v = e[i].v; cur[u] = i;
        if (dep[v] == dep[u] + 1 && e[i].w)
        {
            ll tmp = Dfs(v, min(e[i].w, rest));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            rest -= tmp;
            if (!rest) break;
        }
    }
    return flow - rest;
}

inline ll dinic()
{
    ll ans = 0;
    while (Bfs()) ans += Dfs(s, 1e18);
    return ans;
}

int main()
{
    read(n); read(m); read(s); read(t);
    for (rei i = 1; i <= m; i++)
    {
        ll u, v, w;
        read(u); read(v); read(w);
        add_edge(u, v, w); add_edge(v, u, 0);
    }
    printf("%lld", dinic());
    return 0;
}

费用流

在最大流的基础上增加了边权的限制，使用最短路处理，本质基于 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
71
72
73
74
75
#include <bits/stdc++.h>
#define rei register int
#define N 100010
using namespace std;
typedef long long ll;
const int inf = 1e9;

template <typename T> inline void read(T &x)
{
    x = 0; T f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    x *= f;
}

int n, m, st, ed, head[N], edge_cnt = 1, incf[N], dis[N], pre[N], vis[N], maxflow, mincost;
struct edge {int nxt, v, w, c;} e[N << 1];

inline void add_edge(int u, int v, int w, int c) {e[++edge_cnt].nxt = head[u]; head[u] = edge_cnt; e[edge_cnt].v = v; e[edge_cnt].w = w; e[edge_cnt].c = c;}

inline bool SPFA()
{
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[st] = 0; q.push(st); vis[st] = 1; incf[st] = inf;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for (rei i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (dis[u] + e[i].c < dis[v] && e[i].w)
            {
                dis[v] = dis[u] + e[i].c;
                incf[v] = min(incf[u], e[i].w);
                pre[v] = i;
                if (!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
    return dis[ed] != 1061109567;
}

inline void MCMF()
{
    while (SPFA())
    {
        int x = ed;
        maxflow += incf[ed];
        mincost += dis[ed] * incf[ed];
        int i;
        while (x != st)
        {
            i = pre[x];
            e[i].w -= incf[ed];
            e[i ^ 1].w += incf[ed];
            x = e[i ^ 1].v;
        }
    }
}

int main()
{
    read(n); read(m); read(st); read(ed);
    for (rei i = 1; i <= m; i++)
    {
        int u, v, c, w; read(u); read(v); read(w); read(c);
        add_edge(u, v, w, c); add_edge(v, u, 0, -c);
    }
    MCMF();
    printf("%d %d", maxflow, mincost);
    return 0;
}