struct MCMF { struct edge { int to, cap, cost, rev; //edge() {} //edge(int to, int _cap, int _cost, int _rev) : to(to), cap(_cap), cost(_cost), rev(_rev) {} }; int V, H[maxn + 5], dis[maxn + 5], PreV[maxn + 5], PreE[maxn + 5]; vector<edge> G[maxn + 5]; void init(int n) { V = n; for (int i = 0; i <= V; ++i)G[i].clear(); } void addedge(int from, int to, int cap, int cost) { G[from].emplace_back(edge{to, cap, cost, (int) G[to].size()}); G[to].emplace_back(edge{from, 0, -cost, (int) G[from].size() - 1}); } int mcmf(int s, int t) { int res = 0, flow = 0; fill(H, H + 1 + V, 0); int f = inf; while (f) { priority_queue<pair<int, int> > q; fill(dis, dis + 1 + V, inf); dis[s] = 0; q.push(pair<int, int>(0, s)); while (!q.empty()) { pair<int, int> now = q.top(); q.pop(); int v = now.second, Size; if (dis[v] < -now.first)continue; Size = G[v].size(); for (int i = 0; i < Size; ++i) { edge e = G[v][i]; if (e.cap > 0 && dis[e.to] > dis[v] + e.cost + H[v] - H[e.to]) { dis[e.to] = dis[v] + e.cost + H[v] - H[e.to]; PreV[e.to] = v; PreE[e.to] = i; q.push(pair<int, int>(-dis[e.to], e.to)); } } } if (dis[t] == inf)break; for (int i = 0; i <= V; ++i)H[i] += dis[i]; int d = f; for (int v = t; v != s; v = PreV[v])d = min(d, G[PreV[v]][PreE[v]].cap); f -= d; flow += d; res += d * H[t]; for (int v = t; v != s; v = PreV[v]) { edge &e = G[PreV[v]][PreE[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } } G;