LG P4722 LOJ 127 【模板】最大流 加强版 Solution

Description

给定一个 $n$ 点 $m$ 边的有向网络图，求 $s$ 到 $t$ 的最大流.

Limitations

$1\le n\le 1200$
$1\le m\le 1.2\times 10^5$
$1\le u,v,s,t\le n$
$1\le w<2^{31}$
$1.5\text{s},500\text{MB}\text{(on luogu)}$

Solution

其实不需要 HLPP.
Dinic 在边权差距小的时候跑得较快，所以我们进行分组，对每个 $i\in [0,31)$，将 $w\in [2^i,2^{i+1})$ 的边分为一组，从大到小对，对每组分别跑 Dinic，可以显著加快速度.（跑完的边和下一组一起跑）

但这样还不够，注意到反向边会拖慢 Dinic 速度（因为会退回输送过去的流量）.
对于每组，我们可以先只加正向边跑一遍 Dinic（但是要更新反向边的流量）.
然后在残量网络上一次性加入所有反向边，再跑一遍 Dinic 即可求出正确答案.

效率再次提升，可以通过此题，时间复杂度玄学.

Code

$3.69\text{KB},2.77\text{s},5.15\text{MB}\text{(in total, C++20 with O2)}$（on luogu）
最大流板子需要修改一处（先不加反向边），板子其他部分省略.

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}template<class T>
struct MaxFlow {// ......void addEdge(int u, int v, T c) {g[u].push_back(e.size());e.emplace_back(v, c);// g[v].push_back(e.size());     // 暂时不加反向边e.emplace_back(u, 0);}// ......
};
using Edge = array<int, 3>;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, s, t;scanf("%d %d %d %d", &n, &m, &s, &t), s--, t--;vector<Edge> e(m);for (auto & [u, v, w] : e) scanf("%d %d %d", &u, &v, &w), u--, v--;sort(e.begin(), e.end(), [&](const Edge& a, const Edge& b) { return a[2] > b[2]; });MaxFlow<int> g(n);int ans = 0;for (int tp : {0, 1}) for (int p = 1 << 30, i = 0; p; p /= 2) {while (i < m && e[i][2] >= p) { auto [u, v, w] = e[i];if (tp == 1) g.g[v].push_back(i * 2 + 1);else g.addEdge(u, v, w);i++;}ans += g.flow(s, t);}printf("%d\n", ans);return 0;
}