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;}最小割
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
最后更新于 ,距今已过 74 天
部分内容可能已过时