﻿ [ZJOI2011]最小割（最小割树模板）

### [ZJOI2011]最小割（最小割树模板）

https://www.luogu.com.cn/problem/P3329

Code：

``````#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;

const int N = 6005;

int n, m;
int x, y, z;

int fi[N], to[N], nt[N], r[N], tot = 1;

void link(int x, int y, int z) {
nt[++ tot] = fi[x], to[tot] = y, r[tot] = z, fi[x] = tot;
nt[++ tot] = fi[y], to[tot] = x, r[tot] = z, fi[y] = tot;
}

int dis[N], d[N], d0, S, T;

int bfs() {
fo(i, 0, n) dis[i] = 1e9;
dis[S] = 0, d[d0 = 1] = S;
for(int i = 1; i <= d0; i ++) {
int x = d[i];
for(int j = fi[x]; j; j = nt[j]) if(r[j]) {
int y = to[j];
if(dis[y] == 1e9) {
dis[y] = dis[x] + 1;
d[++ d0] = y;
}
}
}
return dis[T] != 1e9;
}

int dg(int x, int flow) {
if(x == T) return flow;
int use = 0;
for(int i = fi[x]; i; i = nt[i]) if(r[i] && dis[x] + 1 == dis[to[i]]) {
int t = dg(to[i], min(flow - use, r[i]));
use += t, r[i] -= t, r[i ^ 1] += t;
if(use == flow) return use;
}
return use;
}

int mark[N];

void dfs(int x) {
if(mark[x]) return;
mark[x] = 1;
for(int i = fi[x]; i; i = nt[i]) if(r[i])
dfs(to[i]);
}

#define V vector<int>
#define pb push_back
#define re resize
#define si size()

int ans[N][N];

void cl() {
for(int i = 2; i <= tot; i += 2) {
int s = r[i] + r[i ^ 1];
r[i] = r[i ^ 1] = s / 2;
}
}

void dg(V a) {
if(a.si <= 1) return;
cl();
S = a[0], T = a[1];
int sum = 0;
while(bfs()) sum += dg(S, 1 << 30);
fo(i, 1, n) mark[i] = 0;
dfs(S);
fo(i, 1, n) if(mark[i])
fo(j, 1, n) if(!mark[j]) {
if(sum < ans[i][j])
ans[i][j] = ans[j][i] = sum;
}
V b, c; b.clear(); c.clear();
ff(i, 0, a.si) if(mark[a[i]])
b.pb(a[i]); else c.pb(a[i]);
dg(b); dg(c);
}

void cl_e() {
fo(i, 1, n) fi[i] = 0;
tot = 1;
}

int main() {
int T;
scanf("%d", &T);
fo(iT, 1, T) {
cl_e();
scanf("%d %d", &n, &m);
fo(i, 1, m) {
scanf("%d %d %d", &x, &y, &z);
}
fo(i, 1, n) fo(j, 1, n) ans[i][j] = 1e9;
V a; a.re(n);
fo(i, 1, n) a[i - 1] = i;
dg(a);
int q, x;
scanf("%d", &q);
fo(ii, 1, q) {
scanf("%d", &x);
int s = 0;
fo(i, 1, n) fo(j, i + 1, n)
s += ans[i][j] <= x;
pp("%d
", s);
}
hh;
}
}
``````