C++11(clang++ 3.9) 解法, 执行用时: 999ms, 内存消耗: 740K, 提交时间: 2020-07-01 18:12:08

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 855, MAXM = 20005, INF = 0x3f3f3f3f;
struct Graph { int u, v, w; } gra[MAXM];
struct Edge { int to, cap, next; } edge[MAXM];
int head[MAXN], id[MAXN], dis[MAXN], que[MAXN], p[MAXN], q[MAXN], n, m, tot;
set<int> ans;
void addedge(int u, int v, int w) {
	edge[tot] = (Edge) { v, w, head[u] };
	head[u] = tot++;
	edge[tot] = (Edge) { u, w, head[v] };
	head[v] = tot++;
}
int bfs(int s, int t) {
	int he = 0, ta = 0;
	memset(dis, -1, sizeof(dis));
	dis[que[ta++] = s] = 0;
	while (he < ta) {
		int u = que[he++];
		for (int i = head[u]; ~i; i = edge[i].next) {
			int v = edge[i].to;
			if (edge[i].cap > 0 && dis[v] < 0)
				dis[que[ta++] = v] = dis[u] + 1;
		}
	}
	return dis[t] >= 0;
}
int dfs(int u, int t, int f) {
	if (u == t) return f;
	int flow = 0;
	for (int i = id[u]; ~i; i = edge[i].next) {
		int v = edge[i].to;
		if (dis[v] == dis[u] + 1 && edge[i].cap > 0) {
			int d = dfs(v, t, min(f, edge[i].cap));
			if (!d) continue;
			edge[i].cap -= d, edge[i ^ 1].cap += d;
			f -= d, flow += d;
			if (!f) {
				id[u] = i;
				return flow;
			}
		}
	}
	id[u] = -1;
	return flow;
}
int dinic(int s, int t) {
	int flow = 0;
	while (bfs(s, t)) {
		memcpy(id, head, sizeof(id));
		flow += dfs(s, t, INF);
	}
	return flow;
}
void rebuild() {
	memset(head, -1, sizeof(head));
	tot = 0;
	for (int i = 1; i <= m; i++)
		addedge(gra[i].u, gra[i].v, gra[i].w);
}
void solve(int l, int r) {
	if (l == r) return;
	rebuild();
	int s = p[l], t = p[r], tl = l, tr = r, cur = dinic(s, t);
	ans.insert(cur);
	for (int i = l; i <= r; i++)
		if (dis[p[i]] >= 0) q[tl++] = p[i];
		else q[tr--] = p[i];
	for (int i = l; i <= r; i++) p[i] = q[i];
	solve(l, tl - 1), solve(tl, r); 
} 
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &gra[i].u, &gra[i].v, &gra[i].w);
	for (int i = 1; i <= n; i++) p[i] = i;
	solve(1, n);
	printf("%d\n", ans.size());
	return 0;
}