最小割树,但没有树。
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
const int N = 160, M = 6100;
const int INF = 1e8;
int e[M], ne[M], h[N], f[M], idx;
int q[N], d[N], cur[N];
int n, m, Q, S, T;
int ans[N][N];
int a[N], b[N];
bool vis[N];
void insert(int u, int v, int c) {
e[idx] = v, ne[idx] = h[u], f[idx] = c, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = c, h[v] = idx++;
}
bool bfs() {
int hh = 0, tt = -1;
memset(d, -1, sizeof d);
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = h[u]; ~i && flow < limit; i = ne[i]) {
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
void reset() {
for (int i = 0; i < idx; i += 2)
f[i] = f[i ^ 1] = (f[i] + f[i ^ 1]) >> 1;
}
void dfs(int u) {
vis[u] = true;
for (int i = h[u]; ~i; i = ne[i])
if (f[i] && !vis[e[i]])
dfs(e[i]);
}
void solve(int l, int r) {
if (l == r) return;
S = a[l], T = a[r];
int res = dinic();
memset(vis, false, sizeof vis);
dfs(S);
int lc = l - 1, rc = r + 1;
for (int i = 1; i <= n; i++) {
if (!vis[i]) continue;
for (int j = 1; j <= n; j++) {
if (vis[j]) continue;
ans[i][j] = ans[j][i] = min(ans[i][j], res);
}
}
for (int i = l; i <= r; i++)
if (vis[a[i]]) b[++lc] = a[i];
else b[--rc] = a[i];
for (int i = l; i <= r; i++) a[i] = b[i];
reset();
solve(l, lc), solve(rc, r);
}
bool first = true;
void solve() {
if (!first) cout << '\n';
first = false;
cin >> n >> m;
memset(ans, 0x3f, sizeof ans);
memset(h, -1, sizeof h), idx = 0;
while (m--) {
int u, v, c;
cin >> u >> v >> c;
insert(u, v, c);
}
for (int i = 1; i <= n; i++) a[i] = i;
solve(1, n);
cin >> Q;
while (Q--) {
int x;
cin >> x;
int res = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (ans[i][j] <= x) res++;
cout << res << '\n';
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) solve();
return 0;
}
jls😍