286 字
1 分钟
网络流板子

dinic板子

#include <algorithm>
#include <bits/stdc++.h>
#include <iterator>
#include <queue>
#include <set>
#include <unordered_map>
#define N 100005
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define pr pair<int, int>
using namespace std;
int n, m, q, ma, block;
vector<vector<int>> map1;
vector<pr> edges;
const ll mod = 1e9 + 7;
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
map1.assign(n + 5, {});
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
edges.push_back({b, c});
map1[a].push_back(edges.size() - 1);
edges.push_back({a, 0});
map1[b].push_back(edges.size() - 1);
}
vector<int> cur;
vector<int> d;
auto bfs = [&](int st, int en) -> bool {
queue<int> q;
d.assign(n + 5, 0);
q.push(st);
d[st] = 1;
while (q.size()) {
auto x = q.front();
q.pop();
for (auto id : map1[x]) {
auto [y, w] = edges[id];
if (w && !d[y]) {
d[y] = d[x] + 1;
q.push(y);
}
}
}
return d[en];
};
auto dinic = [&](int st, int en) {
auto dfs = [&](auto &&self, int x, ll flow) -> ll {
ll res = 0;
if (x == en)
return flow;
for (auto &i = cur[x]; i < map1[x].size(); i++) {
auto &[v, w] = edges[map1[x][i]];
if (w && d[v] == d[x] + 1) {
auto tem = self(self, v, min(flow, (ll)w));
edges[map1[x][i] ^ 1].second += tem, res += tem, w -= tem, flow -= tem;
}
}
if (!res)
d[x] = 0;
return res;
};
ll res = 0;
while (bfs(st, en)) {
cur.assign(n + 5, {});
res += dfs(dfs, st, 1e9);
}
return res;
};
cout << dinic(1, n);
return 0;
}

最小割

网络流板子
https://sanzenin.top/posts/obsidian/网络流板子/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取