网络流
最大流
struct Edge {
int u, v, c, f, nxt;
} e[maxm << 1];
int G[maxn], edges;
void init() { memset(G, -1, sizeof G); edges = 0; }
void adde(int u, int v, int c) {
e[edges++] = (Edge){u, v, c, 0, G[u]};
G[u] = edges-1;
e[edges++] = (Edge){v, u, 0, 0, G[v]};
G[v] = edges-1;
}
int dis[maxn];
bool bfs(int s, int t) {
memset(dis, -1, sizeof dis);
static int Q[maxn], l, r;
for (l = r = 0, dis[Q[r++] = s] = 0; l < r; ) {
int u = Q[l++];
for (int i = G[u], v; ~i; i = e[i].nxt)
if (v = e[i].v, e[i].f < e[i].c && dis[v] == -1)
dis[Q[r++] = v] = dis[u]+1;
}
return ~dis[t];
}
int cur[maxn];
int dfs(int u, int t, int a) {
if (u == t || !a) return a;
int flow = 0, f;
for (int &i = cur[u], v; ~i; i = e[i].nxt)
if (v = e[i].v, dis[v] == dis[u]+1 && (f = dfs(v, t, std::min(e[i].c-e[i].f, a)))) {
flow += f; e[i].f += f;
e[i^1].f -= f; a -= f;
if (!a) break;
}
return flow;
}
int maxflow(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
rep(i, 1, n) cur[i] = G[i];
flow += dfs(s, t, inf);
}
return flow;
}