#include<iostream>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include <cstring>
typedef long long ll;
using namespace std;
struct Edge {
ll weight;
int end, next;
Edge() {}
Edge(int e, ll w, int n = 0) {
end = e;
weight = w;
next = n;
}
bool operator<(const Edge &a) const {
return (a.weight == weight ? end > a.end : weight > a.weight);
}
};
const int M = int(1e5 + 10);
const int INF = 0x3f3f3f3f;
const int N = 1001;
struct Graph
{
Edge eg[M];
int cnt, head[N];
bool vis[N];
void init(int n) {
cnt = 0;
memset(head, -1, sizeof(int)*n);
}
void addEdge(int i, int j, ll v) {
eg[cnt] = Edge(j, v, head[i]);
head[i] = cnt;
cnt++;
}
} gh;
struct Dinic {
Graph gh;
// 点的范围[0, n)
int n;
// 弧优化
int cur[N], dis[N];
Dinic() {};
// 设置N
void init(int _n) {
n = _n;
gh.init(n);
}
// 加流量
void addFlow(int x, int y, ll f) {
gh.addEdge(x, y, f);
gh.addEdge(y, x, 0);
}
bool bfs(int s, int e) {
memset(dis, -1, sizeof(int) * n);
int q[N];
int l, r;
l = r = 0;
dis[s] = 0;
q[r++] = s;
while (l < r) {
int f = q[l++];
for (int i = gh.head[f]; ~i; i = gh.eg[i].next) {
if (gh.eg[i].weight > 0 && dis[gh.eg[i].end] == -1) {
dis[gh.eg[i].end] = dis[f] + 1;
q[r++] = gh.eg[i].end;
}
}
}
return dis[e] > 0;
}
ll dfs(int s, int e, ll mx) {
if (s == e || mx == 0) {
return mx;
}
ll flow = 0;
for (int &k = cur[s]; ~k; k = gh.eg[k].next) {
auto &eg = gh.eg[k];
ll a;
if (eg.weight > 0 && dis[eg.end] == dis[s] + 1 && (a = dfs(eg.end, e, min(eg.weight, mx)))) {
eg.weight -= a;
gh.eg[k ^ 1].weight += a;
flow += a;
mx -= a;
if (mx <= 0) break;
}
}
return flow;
}
ll max_flow(int s, int e) {
ll ans = 0;
while (bfs(s, e)) {
memcpy(cur, gh.head, sizeof(int) * n);
ans += dfs(s, e, INF);
}
return ans;
}
} dinic;
