P4123 [CQOI2016]不同的最小割

为何只有 10 分？

#include<bits/stdc++.h>
using namespace std;
#define reg register
extern "C" {
namespace io {
#define BUFS 100000
	static char in[BUFS], *p = in, *pp = in;
#define gc() (p == pp && (pp = (p = in) + fread(in, 1, BUFS, stdin), p == pp) ? EOF : *p++)
	inline int read() {
		reg int x = 0; reg char ch, f = 0;
		while (!isdigit(ch = gc())) f |= ch == '-';
		while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return f ? -x : x;
	}
	inline char gtc() {
		reg char ch; while (isspace(ch = gc())); return ch;
	}
}}
#define rd io :: read
#define gtc io :: gtc'
const int N = 1001, M = 10001;
int n, m, tot = 1, head[N], s, t, cur[N], a[N], dep[N];
struct Edge{int v, nxt, w, re;} eg[M << 1];
inline void addedge(int u, int v, int w) {
	eg[++tot] = Edge{v, head[u], w, w}, head[u] = tot;
	eg[++tot] = Edge{u, head[v], 0, 0}, head[v] = tot;
}
queue<int>Q;
inline bool bfs() {
	memset(dep, 0x3f3f3f3f, sizeof dep), dep[s] = 0;
	Q.push(s);
	while (!Q.empty()) {
		reg int u = Q.front(); Q.pop();
		for (reg int i = head[u], v; i; i = eg[i].nxt)
			dep[v = eg[i].v] == 0x3f3f3f3f && eg[i].w > 0 && (
				dep[v] = dep[u] + 1, Q.push(v), 0
			);
	}
	return dep[t] != 0x3f3f3f3f;
}
int dfs(int u, int mn) {
	if (u == t) return mn;
	int a, flw = 0;
	for (reg int i = cur[u], v; i; i = eg[i].nxt) {
		cur[u] = i, v = eg[i].v;
		if (dep[v] == dep[u] + 1 && eg[i].w > 0 && (a = dfs(v, min(eg[i].w, mn - flw)))) {
			eg[i].w -= a, eg[i ^ 1].w += a, flw += a;
			if (flw == mn) break;
		}
	}
	if (!flw) dep[u] = 0x3f3f3f3f;
	return flw;
}
inline bool cmp(int a, int b) {return dep[a] < dep[b];}
set<int> S;
inline void solve(int l, int r) {
	if (l == r) return;
	int res = 0, tp, cut;
	s = a[l], t = a[r];
	while (bfs()) {
		memcpy(cur, head, sizeof head);
		while (tp = dfs(s, 0x3f3f3f3f)) res += tp;
	}
	S.insert(res);
	sort(a + l, a + r + 1, cmp);
	for (reg int i = l; i <= r; ++i) if (dep[a[i]] == 0x3f3f3f3f) {cut = i; break;}
	for (reg int i = 1; i <= tot; ++i) eg[i].w = eg[i].re;
	solve(l, cut - 1), solve(cut, r);
}
int main() {
	n = rd(), m = rd();
	for (reg int i = 1, u, v, w; i <= m; ++i)
		u = rd(), v = rd(), w = rd(), addedge(u, v, w);
	for (reg int i = 1; i <= n; ++i) a[i] = i;
	solve(1, n);
	printf("%d", S.size());
	return 0;
}