Skip to content
TechMind

网络流

Dinic🧀

int🧀

 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
struct dinic
{
    vector<vector<int>> g;
    vector<array<int, 2>> e;
    vector<int> dis, cur;
    int n;

    dinic(int _n)
    {
        n = _n;
        g.resize(n + 1);
    }

    void add(int u, int v, int w)
    {
        g[u].push_back(e.size());
        e.push_back({v, w});
        g[v].push_back(e.size());
        e.push_back({u, 0});
    }

    bool bfs(int s, int t)
    {
        dis.assign(n + 1, -1);
        queue<int> q;
        dis[s] = 0;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto id : g[u])
            {
                auto &[v, c] = e[id];
                if (c && dis[v] == -1)
                {
                    dis[v] = dis[u] + 1;
                    if (v == t)
                        return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    int dfs(int u, int t, int f)
    {
        if (u == t)
            return f;
        int r = f;
        for (int &i = cur[u]; i < (int)g[u].size(); i++)
        {
            int j = g[u][i];
            auto [v, w] = e[j];
            if (w && dis[v] == dis[u] + 1)
            {
                int d = dfs(v, t, min(r, w));
                e[j][1] -= d;
                e[j ^ 1][1] += d;
                r -= d;
                if (r == 0)
                    return f;
            }
        }
        return f - r;
    }

    int work(int s, int t)
    {
        int ret = 0;
        while (bfs(s, t))
        {
            cur.assign(n + 1, 0);
            ret += dfs(s, t, inf);
        }
        return ret;
    }

    auto edge() // from/to/flow/cap
    {
        vector<array<int, 4>> ret;
        for (int i = 0; i < e.size(); i += 2)
            ret.pb({e[i ^ 1][0], e[i][0], e[i ^ 1][1], e[i ^ 1][1] + e[i][1]});
        return ret;
    }
};

double🧀

 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
using pid = pair<int, double>;

struct dinic
{
    int n;
    vec<vec<int>> g;
    vec<pid> e;
    vec<int> dis, cur;

    dinic(int _n)
    {
        n = _n;
        g.resize(n + 1);
    }

    void add(int u, int v, double w)
    {
        g[u].pb(e.size());
        e.pb({v, w});
        g[v].pb(e.size());
        e.pb({u, 0});
    }

    bool bfs(int s, int t)
    {
        dis.assign(n + 1, -1);
        queue<int> q;
        dis[s] = 0;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto i : g[u])
            {
                auto &[v, c] = e[i];
                if (c > 0 && dis[v] == -1)
                {
                    dis[v] = dis[u] + 1;
                    if (v == t)
                        return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    double dfs(int u, int t, double f)
    {
        if (u == t)
            return f;
        double r = f;
        double res = 0;
        for (int &i = cur[u]; i < (int)(g[u].size()); i++)
        {
            int j = g[u][i];
            auto &[v, c] = e[j];
            if (c > 0 && dis[v] == dis[u] + 1)
            {
                double temp = dfs(v, t, min(r, c));
                res += temp;
                e[j].sec -= temp;
                e[j ^ 1].sec += temp;
                r -= temp;
                if (r <= eps)
                    return f;
            }
        }
        return res;
    }

    double work(int s, int t)
    {
        double ans = 0;
        while (bfs(s, t))
        {
            cur.assign(n + 1, 0);
            ans += dfs(s, t, 1e100);
        }
        return ans;
    }
};

mcmf🧀

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
struct mcmf
{
    vector<vector<int>> g;
    vector<array<int, 3>> e;
    vector<int> dis, pre;
    vector<short> vis;
    int n;

    mcmf(int _n)
    {
        n = _n;
        g.resize(n + 1);
    }

    void add(int u, int v, int f, int c)
    {
        g[u].push_back(e.size());
        e.push_back({v, f, c});
        g[v].push_back(e.size());
        e.push_back({u, 0, -c});
    }

    bool spfa(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        vis.assign(n + 1, 0);
        queue<int> q;
        dis[s] = 0, vis[s] = 1;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop(), vis[u] = 0;
            for (auto id : g[u])
            {
                auto [v, f, c] = e[id];
                if (f && dis[u] + c < dis[v])
                {
                    pre[v] = id;
                    dis[v] = dis[u] + c;
                    if (!vis[v])
                        q.push(v), vis[v] = 1;
                }
            }
        }
        return dis[t] != inf;
    }

    auto work(int s, int t)
    {
        array<int, 2> ret = {0, 0};
        while (spfa(s, t))
        {
            int flow = inf;
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
                flow = min(flow, e[pre[i]][1]);
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
            {
                e[pre[i]][1] -= flow;
                e[pre[i] ^ 1][1] += flow;
            }
            ret[0] += flow;
            ret[1] += flow * dis[t];
        }
        return ret;
    }

    auto edge() // u, v, f, cap, cost
    {
        vector<array<int, 5>> ret;
        for (int i = 0; i < e.size(); i += 2)
            ret.pb({e[i ^ 1][0], e[i][0], e[i ^ 1][1], e[i][1] + e[i ^ 1][1], e[i][2]});
        return ret;
    }
};

dijk+原始对偶🧀

 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
struct mcmf
{
    vec<aiii> e; // to,cap,cost
    vec<vec<int>> g;
    vec<int> h, dis, pre;
    int n;
    mcmf(int _n)
    {
        n = _n;
        g.resize(n + 1);
        h.resize(n + 1);
    }

    void add(int u, int v, int w, int c)
    {
        g[u].pb(e.size());
        e.pb({v, w, c});
        g[v].pb(e.size());
        e.pb({u, 0, -c});
    }

    bool dijkstra(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        priority_queue<aii, vec<aii>, greater<aii>> q;
        dis[s] = 0;
        q.push({0, s});
        while (!q.empty())
        {
            auto [d, u] = q.top();
            q.pop();
            if (dis[u] != d)
                continue;
            for (auto i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > 0 && dis[v] > d + h[u] - h[v] + c)
                {
                    dis[v] = d + h[u] - h[v] + c;
                    pre[v] = i;
                    q.push({dis[v], v});
                }
            }
        }
        return dis[t] != inf;
    }

    aii work(int s, int t)
    {
        aii ret = {0, 0}; // flow,cost
        while (dijkstra(s, t))
        {
            for (int i = 1; i <= n; i++)
                h[i] += dis[i];
            int aug = inf;
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
                aug = min(aug, e[pre[i]][1]);
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
            {
                e[pre[i]][1] -= aug;
                e[pre[i] ^ 1][1] += aug;
            }
            ret[0] += aug;
            ret[1] += aug * h[t];
        }
        return ret;
    }
};

spfa初始化+dijk+原始对偶🧀

  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
109
struct mcmf
{
    vec<aiii> e; // to,cap,cost
    vec<vec<int>> g;
    vec<int> h, dis, pre;
    int n;
    mcmf(int _n)
    {
        n = _n;
        g.resize(n + 1);
        h.resize(n + 1);
    }

    void add(int u, int v, int w, int c)
    {
        g[u].pb(e.size());
        e.pb({v, w, c});
        g[v].pb(e.size());
        e.pb({u, 0, -c});
    }

    bool spfa(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        vec<char> inq(n + 1, 0);
        queue<int> q;
        dis[s] = 0;
        q.push(s);
        inq[s] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (auto i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > 0 && dis[v] > dis[u] + c)
                {
                    dis[v] = dis[u] + c;
                    pre[v] = i;
                    if (!inq[v])
                    {
                        q.push(v);
                        inq[v] = 1;
                    }
                }
            }
        }
        return dis[t] != inf;
    }

    bool dijkstra(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        priority_queue<aii, vec<aii>, greater<aii>> q;
        dis[s] = 0;
        q.push({0, s});
        while (!q.empty())
        {
            auto [d, u] = q.top();
            q.pop();
            if (dis[u] != d)
                continue;
            for (auto i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > 0 && dis[v] > d + h[u] - h[v] + c)
                {
                    dis[v] = d + h[u] - h[v] + c;
                    pre[v] = i;
                    q.push({dis[v], v});
                }
            }
        }
        return dis[t] != inf;
    }

    aii work(int s, int t)
    {
        aii ret = {0, 0};
        if (!spfa(s, t))
            return ret;
        for (int i = 1; i <= n; i++)
            if (dis[i] < inf)
                h[i] = dis[i];
        while (1)
        {
            int aug = inf;
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
                aug = min(aug, e[pre[i]][1]);
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
            {
                e[pre[i]][1] -= aug;
                e[pre[i] ^ 1][1] += aug;
            }
            ret[0] += aug;
            ret[1] += aug * h[t];
            if (!dijkstra(s, t))
                break;
            for (int i = 1; i <= n; i++)
                if (dis[i] < inf)
                    h[i] += dis[i];
        }
        return ret;
    }
};

one flow fits all究极轮椅版🧀

  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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
template <typename TF, typename TC>
struct mcmf
{
    struct Edge
    {
        int to;
        TF cap;
        TC cost;
    };

    vector<Edge> e;
    vector<vector<int>> g;
    vector<TC> h, dis;
    vector<int> pre;
    int n;

    const TC INF_COST = numeric_limits<TC>::max() / 2;
    const TF INF_FLOW = numeric_limits<TF>::max() / 2;

    mcmf(int _n)
    {
        n = _n;
        g.resize(n + 1);
    }

    void add(int u, int v, TF w, TC c)
    {
        g[u].push_back(e.size());
        e.push_back({v, w, c});
        g[v].push_back(e.size());
        e.push_back({u, 0, -c});
    }

    bool spfa(int s)
    {
        h.assign(n + 1, INF_COST);
        vector<char> inq(n + 1, 0);
        vector<int> cnt(n + 1, 0);
        queue<int> q;
        TF eps_flow = 0;
        if constexpr (is_floating_point_v<TF>)
            eps_flow = 1e-9;
        TC eps_cost = 0;
        if constexpr (is_floating_point_v<TC>)
            eps_cost = 1e-9;
        h[s] = 0;
        q.push(s);
        inq[s] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (int i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > eps_flow && h[v] > h[u] + c + eps_cost)
                {
                    h[v] = h[u] + c;
                    if (!inq[v])
                    {
                        q.push(v);
                        inq[v] = 1;
                        cnt[v]++;
                        if (cnt[v] >= n)
                            return 0; 
                    }
                }
            }
        }
        return 1;
    }

    bool dijkstra(int s, int t)
    {
        dis.assign(n + 1, INF_COST);
        pre.assign(n + 1, -1);
        using P = pair<TC, int>;
        priority_queue<P, vector<P>, greater<P>> q;
        TF eps_flow = 0;
        if constexpr (is_floating_point_v<TF>)
            eps_flow = 1e-9;
        TC eps_cost = 0;
        if constexpr (is_floating_point_v<TC>)
            eps_cost = 1e-9;
        dis[s] = 0;
        q.push({0, s});
        while (!q.empty())
        {
            auto [d, u] = q.top();
            q.pop();
            if (dis[u] < d - eps_cost)
                continue;
            for (int i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > eps_flow && dis[v] > d + h[u] - h[v] + c + eps_cost)
                {
                    dis[v] = d + h[u] - h[v] + c;
                    pre[v] = i;
                    q.push({dis[v], v});
                }
            }
        }
        return dis[t] < INF_COST / 2;
    }

    pair<TF, TC> work(int s, int t)
    {
        if (!spfa(s))
            return {-1, -1};
        TF flow = 0;
        TC cost = 0;
        TF eps_flow = 0;
        if constexpr (is_floating_point_v<TF>)
            eps_flow = 1e-9;
        while (dijkstra(s, t))
        {
            for (int i = 1; i <= n; i++)
                if (dis[i] < INF_COST / 2)
                    h[i] += dis[i];
            TF aug = INF_FLOW;
            for (int i = t; i != s; i = e[pre[i] ^ 1].to)
                aug = min(aug, e[pre[i]].cap);
            if (aug <= eps_flow)
                break;
            for (int i = t; i != s; i = e[pre[i] ^ 1].to)
            {
                e[pre[i]].cap -= aug;
                e[pre[i] ^ 1].cap += aug;
            }
            flow += aug;
            cost += h[t] * aug;
        }
        return {flow, cost};
    }

    vector<tuple<int, int, TF, TF, TC>> edge() // from,to,flow,cap,cost
    {
        vector<tuple<int, int, TF, TF, TC>> ret;
        for (int i = 0; i < (int)e.size(); i += 2)
            ret.push_back({e[i ^ 1].to, e[i].to, e[i ^ 1].cap, e[i].cap + e[i ^ 1].cap, e[i].cost});
        return ret;
    }
};

有源汇/无源汇上下界可行流🧀

可转化为最大流问题。

建图时添加源点 \(SS\) ，汇点 \(TT\) 。

连边方法：

  • 对于原图中存在的边 {u,v,l,r} ，连 {u,v,r-l} 。
  • 对于原图中每一个点 ,令 d[u] 代表u点的所有入边的流量下界减去出边的流量下界。
  • 如果 d[u]<0 ，连边{u,TT,-d[u]} 。
  • 如果 d[u]>0 ，连边{SS,u,d[u]} 。
  • 对于有源汇问题，连边 {T,S,inf,0}。在后文中，这条边被简称为inf 边。（注意：这里的 \(S\) ，\(T\) 是原图源汇点，而非新增的附加源汇点。）

如果图中所有与 \(SS\) 相连的边均满流，则表明存在可行流，每条边具体流量为该边流量下界加上其在新图中对应边的流量。

有源汇上下界最大流/最小流🧀

先跑一遍可行流。如果存在可行流，记录答案 ans1，大小为 inf 边实际流量。

最大流🧀

在可行流基础上，删除先前连接的 inf 边，以原图源汇点（不是附加源汇点）为新的源汇再跑一遍最大流，记录答案 ans2 。

最终答案为 ans1 + ans2 。

最小流🧀

在可行流基础上，删除先前连接的 inf 边，以原图源点（不是附加源点）为新汇点，以原图汇点（不是附加汇点）为新源点再跑一遍最大流，记录答案 ans2 。

最终答案为 ans1 - ans2 。

有源汇/无源汇上下界最小费用可行流🧀

可转化为费用流问题。

建图时添加源点 \(SS\) ，汇点 \(TT\) 。

连边方法：

  • 对于原图中存在的边 {u,v,l,r,c} ，连 {u,v,r-l,c} 。

  • 对于原图中每一个点（包括源汇）\(u\) ,令 d[u] 代表u点的所有入边的流量下界减去出边的流量下界。

  • 如果 d[u]<0 ，连边{u,TT,-d[u],0} 。

  • 如果 d[u]>0 ，连边{SS,u,d[u],0} 。

  • 对于有源汇问题，连边 {T,S,inf,0}。（注意：这里的 \(S\) ，\(T\) 是原图源汇点，而非新增的附加源汇点。）

如果想要限制 \(S\) 到 \(T\) 的总流量不超过 \(f\) ，可以将这条边的流量改为 \(f\) 。

如果图中所有与 \(SS\) 相连的边均满流，则表明存在可行流，每条边具体流量为该边流量下界加上其在新图中对应边的流量。

最小总费用 \(=\) （新图 \(SS \to TT\) 跑出的最小费用） \(+\) \(\sum (l \times c)\)。