XCPC wiki - 网络流

在一个有向图上选择一个源点 (s)，一个汇点 (t)，每一条边上都有一个流量上限（以下称为容量 ©），即经过这条边的流量不能超过这个上界，同时，除源点和汇点外，所有点的入流和出流都 相等，而源点只有流出的流，汇点只有汇入的流。

最大流（Max-flow）

使得流的值最大的流函数被称为网络的最大流 , 此时的 流的值被称为网络的最大流量。

Ford-Fulkerson Algorithm

一句话概括：添加反向边使流量可以回退。

共有$m$ 条边，最大流量为$f$ ，每一次循环至少会让最大流增大一份，故时间复杂度最坏情况下为$O(f·m)$。

Edmonds-Karp Algorithm

为对 FF 的优化：在寻找简单路径时将图视为边权为 1 的无向图并对其跑最短路，即 BFS。（这里也可以理解为 EK 算法是 FF 算法的一种实现，因为 FF 算法并没有对路径选择有任何约束。）

共有$n$ 个点，$m$ 条边时，残余图最多有$m$ 条反向边总共$2·m$ 条边，每一轮最短路需要$O(m)$，最多循环$(m·n)$ 轮（证明复杂）。故时间复杂度为$O(m^{2}·n)$，与最大流量无关。

Dinic Algorithm

通过 bfs 建立 level 图对原图进行分层，且 level 图仅保存相邻两层之间的边。

• 创建剩余图
• while (建立 level 图) { 寻找阻塞流，添加反向边，更新剩余图; }
  有理论证明最多循环$(n-1)$ 轮，每一轮需要$O(m·n)$，**故时间复杂度为$O(m·n^{2})$

struct MaxFlow {
    vector<vector<array<int, 3>>> E;
    vector<int> level, curr;

    MaxFlow(int n) : E(n), level(n), curr(n) {}

    void add(int u, int v, int w) {
        E[u].push_back({ w, v, int(E[v].size()) });
        E[v].push_back({ 0, u, int(E[u].size()) - 1 });
    }

    bool bfs(int s, int t) {
        queue<int> q;
        fill(level.begin(), level.end(), 0);
        fill(curr.begin(), curr.end(), 0);
        level[s] = 1;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto& [w, v, id] : E[u]) {
                if (w && !level[v]) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] > 0;
    }

    int dfs(int u, int t, int maxf) {
        if (u == t) return maxf;
        for (int& i = curr[u]; i < E[u].size(); i++) {
            auto& [w, v, id] = E[u][i];
            if (w && (level[v] == level[u] + 1)) {
                int f = dfs(v, t, min(maxf, w));
                if (f) {
                    w -= f;
                    E[v][id][0] += f;
                    curr[u] = i;
                    return f;
                }
            }
        }
        return 0;
    }

    int dinic(int s, int t) {
        int ans = 0;
        while (bfs(s, t)) {
            while (int f = dfs(s, t, 1e9)) {
                ans += f;
            }
        }
        return ans;
    }
};

CCPC 2024 网络赛 G - 疯狂星期六

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N = 5e4 + 10;

vector<tuple<ll, int, int>> E[N];
int level[N];
int curr[N];

void add(int u, int v, ll w) {
    E[u].push_back({ w, v, E[v].size() });
    E[v].push_back({ 0, u, E[u].size() - 1 });
}

bool bfs(int s, int t) {
    queue<int> q;
    memset(level, 0, sizeof level);
    memset(curr, 0, sizeof curr);
    level[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto& [w, v, id] : E[u]) {
            if (w && !level[v]) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] > 0;
}

ll dfs(int u, int t, ll maxf) {
    if (u == t) return maxf;
    for (int& i = curr[u]; i < E[u].size(); ++i) {
        auto& [w, v, id] = E[u][i];
        if (w && (level[v] == level[u] + 1)) {
            ll f = dfs(v, t, min(maxf, w));
            if (f) {                   // 有增广路
                w -= f;                // 正向边减去f
                get<0>(E[v][id]) += f; // 反向边减去f
                curr[u] = i;           // 更新当前弧
                return f;              // 返回f
            }
        }
    }
    return 0; // 没有增广路
}

ll dinic(int s, int t) {
    ll ans = 0;
    while (bfs(s, t)) {
        while (ll f = dfs(s, t, 1e18)) {
            ans += f;
        }
    }
    return ans;
}

int n, m;
int s = 0, t = 0;
int a[N], val[N];
int x[N], y[N], z[N];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> val[i];
    }
    int yyq = val[1];
    int yyqmax = 0;
    ll sum = 0;
    s = 0, t = n + m + 1;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i] >> z[i];
        sum += z[i];

        if (x[i] == 1 || y[i] == 1) {
            yyq += z[i];
            yyqmax = min(yyq, a[1]);
        }
    }
    yyqmax = min(yyq, a[1]);
    for (int i = 1; i <= m; i++) {
        add(s, i, z[i]); // 源点到每个菜品的容量
        add(i, x[i] + m, z[i]); // 菜品到人的容量
        add(i, y[i] + m, z[i]); // 菜品到人的容量
    }
    for (int i = 1; i <= n; i++) {
        int x = min(a[i], yyqmax - (i != 1)) - val[i];
        if (x > 0) {
            add(i + m, t, x);
        }
        if (x < 0) {
            cout << "NO" << endl;
            return 0;
        }
    }
    if (dinic(s, t) == sum) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

CF1082G 最大子图权值

int n, m;
cin >> n >> m;

MaxFlow maxflow(n + m + 5);

int s = 0;
int t = n + m + 1;
for (int i = 1; i <= n; i++) {
	int tmp;
	cin >> tmp;
	maxflow.add(s, i, tmp);
}
ll maxx = 0;
for (int i = 1; i <= m; i++) {
	int u, v, w;
	cin >> u >> v >> w;
	maxflow.add(u, n + i, 1e18);
	maxflow.add(v, n + i, 1e18);
	maxflow.add(n + i, t, w);
	maxx += w;
}

maxx -= maxflow.dinic(s, t);
if (maxx < 0) maxx = 0;
cout << maxx << endl;

2023 ICPC 济南 E - 二分图匹配加边

[[…/contests/VP/2024-10-07-Autumn6-2023ICPC济南|2024-10-07-Autumn6-2023ICPC济南]]

• WA14: cntl * cntr 爆 int
• TLE18: w 开 ll 没必要
• TLE: dinic 被卡了

int n, m;
cin >> n >> m;

MaxFlow maxflow(2 * n + 2);

int s = 0;
int t = 2 * n + 1;
for (int i = 1; i <= n; i++) {
	maxflow.add(s, i, 1);
	maxflow.add(i + n, t, 1);
}
while (m--) {
	int x, y;
	cin >> x >> y;
	maxflow.add(x, y + n, 1);
}
maxflow.dinic(s, t);

int cntl = 0, cntr = 0;
vector<int> vis(2 * n + 2);
auto dfs1 = [&](this auto&& self, int u) -> void {
	vis[u] = 1;
	for (auto [w, v, id] : maxflow.E[u]) {
		if (vis[v] == 1 || w == 0) continue;
		if (v >= 1 && v <= n) cntl++;
		self(v);
	}
	return;
};
dfs1(s);

fill(vis.begin(), vis.end(), 0);
auto dfs2 = [&](this auto&& self, int u) -> void {
	vis[u] = 1;
	for (auto [w, v, id] : maxflow.E[u]) {
		if (vis[v] == 1 || w != 0) continue;
		if (n + 1 <= v && v <= n + n) cntr++;
		self(v);
	}
	return;
};
dfs2(t);

cout << (1ll * cntl * cntr) << "\n";

以上代码需要一些卡时技巧，使用 HK 实现更优的复杂度：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;

struct MaxMatch {
    int n, m, dis;
    vector<vector<int>> E;
    vector<int> nx, ny, dx, dy, vis;

    MaxMatch(int n, int m) : n(n), m(m), dis(0), E(n), nx(n, -1), ny(m, -1), dx(n), dy(m), vis(m) {}

    void add(int u, int v) {
        E[u].push_back(v);
    }

    bool bfs() {
        dis = inf;
        fill(dx.begin(), dx.end(), -1);
        fill(dy.begin(), dy.end(), -1);
        queue<int> Q;
        for (int i = 0; i < n; ++i) {
            if (nx[i] == -1) Q.push(i), dx[i] = 0;
        }
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            if (dx[u] > dis) break;
            for (auto v : E[u]) {
                if (dy[v] == -1) {
                    dy[v] = dx[u] + 1;
                    if (ny[v] == -1) dis = dy[v];
                    else dx[ny[v]] = dy[v] + 1, Q.push(ny[v]);
                }
            }
        }
        return dis != inf;
    }

    bool dfs(int u) {
        for (auto v : E[u]) {
            if (!vis[v] && dy[v] == dx[u] + 1) {
                vis[v] = true;
                if (ny[v] != -1 && dy[v] == dis) continue;
                if (ny[v] == -1 || dfs(ny[v])) {
                    ny[v] = u;
                    nx[u] = v;
                    return true;
                }
            }
        }
        return false;
    }

    int work() {
        int res = 0;
        while (bfs()) {
            fill(vis.begin(), vis.end(), false);
            for (int i = 0; i < n; ++i) {
                if (nx[i] == -1 && dfs(i)) ++res;
            }
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, e;
        cin >> n >> e;

        MaxMatch G(n, n);

        while (e--) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            G.add(u, v);
        }
        G.work();

        vector<vector<pair<int, int>>> E(2 * n + 2);
        int s = 2 * n, t = 2 * n + 1;
        for (int u = 0; u < n; ++u) {
            if (G.nx[u] == -1) {
                E[s].push_back({ 1, u });
                E[u].push_back({ 0, s });
            } else {
                E[s].push_back({ 0, u });
                E[u].push_back({ -1, s });
            }
        }
        for (int v = 0; v < n; ++v) {
            if (G.ny[v] == -1) {
                E[v + n].push_back({ 1, t });
                E[t].push_back({ 0, v + n });
            } else {
                E[v + n].push_back({ 0, t });
                E[t].push_back({ -1, v + n });
            }
        }
        for (int u = 0; u < n; ++u) {
            for (auto v : G.E[u]) {
                if (G.nx[u] == v) {
                    E[u].push_back({ 0, v + n });
                    E[v + n].push_back({ -1, u });
                } else {
                    E[u].push_back({ 1, v + n });
                    E[v + n].push_back({ 0, u });
                }
            }
        }

        int cntl = 0, cntr = 0;
        vector<int> vis(2 * n + 2);

        auto dfs1 = [&](this auto&& self, int u) -> void {
            vis[u] = 1;
            for (auto [w, v] : E[u]) {
                if (vis[v] || w == 0) continue;
                self(v);
            }
            return;
        };
        dfs1(2 * n);
        for (int u = 0; u < n; ++u) {
            cntl += vis[u];
        }

        fill(vis.begin(), vis.end(), 0);
        auto dfs2 = [&](this auto&& self, int u) -> void {
            vis[u] = 1;
            for (auto [w, v] : E[u]) {
                if (vis[v] || w) continue;
                self(v);
            }
            return;
        };
        dfs2(2 * n + 1);
        for (int u = n; u < n + n; ++u) {
            cntr += vis[u];
        }

        cout << (1ll * cntl * cntr) << "\n";
    }

    return 0;
}

CF2026E. Best Subsequence

题意 最大化子序列的长度减去按位或的 popcount。数据范围：$n \leqslant 100,\ 0 \leqslant a_{i}<2^{60}$。

思路 每个东西有选或不选两种状态，而且每个东西都状态确定，价值也相应确定。

赛时考虑过 DP，但每个数之间关系很强，很难转移；考虑过字典树，但本题每个二进制位是独立的，字典树强加了一个顺序；考虑过连边跑最短路，但这种方法适用于二者的关系，而不是很多数之间的关系。

画出了 01 矩阵（行是数，列是二进制位），很像二分图，又不是最大匹配，所以想换一种连边方式跑最大流。

选择一个二进制位，损失为 1，不选一个数，损失为 1，理想情况是 n，求最小损失。

从源点向每个数连边权为 1 的边，从每个二进制位向汇点连边权为 1 的边，对于每个数，如果某个二进制位为 1，则由这个数向二进制位连边权为无穷的边。则最小损失是最小割。

答案为理想情况减去最小损失。

点数$n+60$，边数$60n$，$100$ 组数据，复杂度可以通过。

int n;
cin >> n;
MaxFlow G(n + 62);
int s = n + 60, t = n + 61;
for (int i = 0; i < n; i++) {
    ll x;
    cin >> x;
    G.add(s, i, 1);
    for (int bit = 0; bit < 60; bit++) {
        if (x >> bit & 1) {
            G.add(i, n + bit, 1e9);
        }
    }
}
for (int bit = 0; bit < 60; bit++) {
    G.add(n + bit, t, 1);
}
cout << n - G.dinic(s, t) << "\n";   

费用流

最小费用最大流

template<class T>
struct MinCostFlow {
    struct Edge {
        int to;
        T w;
        T cost;
        Edge(int to, T w, T cost) : to(to), w(w), cost(cost) {};
    };

    int n;
    vector<Edge> e;
    vector<vector<int>> E;

    MinCostFlow(int n) : n(n), E(n) {}

    void add(int u, int v, T w, T cost) {
        E[u].push_back(e.size());
        e.push_back({ v, w, cost });
        E[v].push_back(e.size());
        e.push_back({ u, 0, -cost });
    }

    vector<T> h, dis;
    vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, numeric_limits<T>::max());
        pre.assign(n, -1);
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> 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 : E[u]) {
                auto [v, w, cost] = e[i];
                if (w > 0 && dis[v] > d + h[u] - h[v] + cost) {
                    dis[v] = d + h[u] - h[v] + cost;
                    pre[v] = i;
                    Q.push({ dis[v], v });
                }
            }
        }
        return dis[t] != numeric_limits<T>::max();
    }

    pair<T, T> flow(int s, int t) {
        T flow = 0, cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; i++) {
                h[i] += dis[i];
            }
            T aug = numeric_limits<int>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                aug = min(aug, e[pre[i]].w);
            }
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                e[pre[i]].w -= aug;
                e[pre[i] ^ 1].w += aug;
            }
            flow += aug;
            cost += aug * h[t];
        }
        return make_pair(flow, cost);
    }

    struct newEdge {
        int from;
        int to;
        T cap;
        T cost;
        T flow;
    };
    vector<newEdge> edges() {
        vector<newEdge> a;
        for (int i = 0; i < e.size(); i += 2) {
            newEdge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.cost = e[i].cost;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

void add(int u, int v, int c, int f) {  // 可行流
    if (f < 0) {
        E[u].push_back(e.size());
        e.emplace_back(v, 0, f);
        E[v].push_back(e.size());
        e.emplace_back(u, c, -f);
    } else {
        E[u].push_back(e.size());
        e.emplace_back(v, c, f);
        E[v].push_back(e.size());
        e.emplace_back(u, 0, -f);
    }
}
void add(int u, int v, int c, int f) {  // 最大流
    E[u].push_back(e.size());
    e.emplace_back(v, c, f);
    E[v].push_back(e.size());
    e.emplace_back(u, 0, -f);
}

2024 ICPC 成都 K. Magical Set

给定集合，每次操作删去一数，插入其因子，集合中元素不可重，问最大操作次数。数据范围：$n \leqslant 300,\ 0 \leqslant a_{i} \leqslant 10^{9}$。

集合中可能出现的每个数向其因子连容量为无穷，费用为 1 的边；建超级源点，向初始集合的每个数连容量为 1，费用为 0 的边；建超级汇点，从集合中可能出现的每个数向其连容量为 1，费用为 0 的边。答案为最大费用最大流。

int n;
cin >> n;

vector<array<int, 4>> edge;
set<int> Q;
Q.insert(1);
int s = 2e9, t = s + 1;

for (int i = 0; i < n; i++) {
	int x;
	cin >> x;
	Q.insert(x);

	edge.push_back({ s, x, 1, 0 });
}

map<int, int> ver;
while (!Q.empty()) {
	auto u = *Q.rbegin(); Q.erase(prev(Q.end()));
	ver[u] = ver.size();
	if (u == 1) continue;

	vector<int> factor;
	for (int i = 1; i * i <= u; i++) {
		if (u % i == 0) {
			factor.push_back(i);
			if (i != u / i) factor.push_back(u / i);
		}
	}

	for (int i = 0; i < factor.size(); i++) {
		int v = factor[i];
		if (u == v) continue;
		edge.push_back({ u, v, inf, -1 });
		Q.insert(v);
	}
}

for (auto& [k, v] : ver) {
	edge.push_back({ k, t, 1, 0 });
}

s = ver[s] = ver.size();
t = ver[t] = ver.size();

MinCostFlow<int> G(ver.size());
for (auto [u, v, w, cost] : edge) {
	u = ver[u], v = ver[v];
	G.add(u, v, w, cost);
}

auto [flow, cost] = G.flow(s, t);
cout << (-cost) << endl;

上述连边方法边数和点数皆巨大，无法通过，需要优化。

我们只关心 始态 和 末态，因此只需从初始集合向最终集合中的点，即其因子连边，这时费用不再是 1，而是最多操作次数。现在的边数是$\sum d(a_{i})$，当$a_{i}$ 是较大的含因子较多的数时，边数仍然巨大。

事实上，只需保留每个数的最小的$n$ 个因子。这样的边数是严格不超过$n^{2}$ 的，复杂度可以通过。

int n;
cin >> n;

vector<array<int, 4>> edge;
int s = 2e9, t = s + 1;

map<int, int> ver;
for (int i = 0; i < n; i++) {
	int x;
	cin >> x;
	if (!ver.count(x)) ver[x] = ver.size();

	auto divisor = getdivisor(x);
	int xsum = divisor.back()[1];

	for (int i = 0; i < n && i < divisor.size() - 1; i++) {
		auto [y, ysum] = divisor[i];
		if (!ver.count(y)) ver[y] = ver.size();
		edge.push_back({ x, y, inf, xsum - ysum });
	}
	edge.push_back({ s, x, 1, 0 });
}

for (auto [x, _] : ver) {
	edge.push_back({ x, t, 1, 0 });
}

s = ver[s] = ver.size();
t = ver[t] = ver.size();

MinCostFlow<int> G(ver.size());
for (auto [u, v, w, cost] : edge) {
	u = ver[u], v = ver[v];
	G.add(u, v, w, -cost);
}

auto [flow, cost] = G.flow(s, t);
cout << (-cost) << endl;