题意
给定一张图，\(q\) 次询问，每次询问两点的最小割。
Sol
最小割树模板题。
考虑去分治一个集合 \(S\)。
每次在里面随便找两个点作为源点和汇点，然后在原图上跑最小割。
然后在残量网络上标记源点集和汇点集。
分别放到两个不同的集合，然后继续分治下去即可。
Code
namespace Mft {
bitset <N> vis;
void dfs(int x) {
vis[x] = 1;
for (int i = G::fir[x]; i; i = G::nex[i]) {
if (!G::cap[i] || vis[G::to[i]]) continue;
dfs(G::to[i]);
}
}
void solve(vector <int> &isl, int n, int m) {
if (isl.size() <= 1) return;
pii st = make_pair(isl.front(), isl.back());
G::fir.fill(0), G::cnt = 1;
for (int i = 1; i <= m; i++) {
int x, y, z; tie(x, y, z) = qrl[i];
G::_add(x, y, z), G::_add(y, x, z);
}
vis = 0;
int len = Mfl::dinic(st);
dfs(st.fi);
vector <int> lpr, rpl;
for (auto x : isl) {
vis[x] ? lpr.push_back(x) : rpl.push_back(x);
}
T::add(st.fi, st.se, len);
T::add(st.se, st.fi, len);
solve(lpr, n, m), solve(rpl, n, m);
}
}
int dfs(int x, int y, int fa) {
int ans = (x == y ? inf : -1);
for (int i = T::fir[x]; i; i = T::nex[i]) {
if (T::to[i] == fa) continue;
int flow = dfs(T::to[i], y, x);
if (~flow) ans = min(flow, T::len[i]);
}
return ans;
}
signed main() {
int n = read() + 1, m = read();
for (int i = 1; i <= m; i++) {
int x = read() + 1, y = read() + 1, z = read();
qrl[i] = make_tuple(x, y, z);
}
vector <int> tp;
for (int i = 1; i <= n; i++)
tp.push_back(i);
Mft::solve(tp, n, m);
int q = read();
while (q--) {
int x = read() + 1, y = read() + 1;
write(dfs(x, y, 0)), puts("");
}
return 0;
}