#include using namespace std; typedef long long ll; struct Edge { int u, v; ll cap, flow; Edge() {} Edge(int u, int v, ll cap): u(u), v(v), cap(cap), flow(0) {} }; struct Dinic { int N; vector E; vector> g; vector d, pt; Dinic(int N): N(N), E(0), g(N), d(N), pt(N) {} void AddEdge(int u, int v, ll cap) { if (u != v) { E.emplace_back(u, v, cap); g[u].emplace_back(E.size() - 1); E.emplace_back(v, u, 0); g[v].emplace_back(E.size() - 1); } } bool BFS(int S, int T) { queue q({S}); fill(d.begin(), d.end(), N + 1); d[S] = 0; while(!q.empty()) { int u = q.front(); q.pop(); if (u == T) break; for (int k: g[u]) { Edge &e = E[k]; if (e.flow < e.cap && d[e.v] > d[e.u] + 1) { d[e.v] = d[e.u] + 1; q.emplace(e.v); } } } return d[T] != N + 1; } ll DFS(int u, int T, ll flow = -1) { if (u == T || flow == 0) return flow; for (int &i = pt[u]; i < g[u].size(); ++i) { Edge &e = E[g[u][i]]; Edge &oe = E[g[u][i]^1]; if (d[e.v] == d[e.u] + 1) { ll amt = e.cap - e.flow; if (flow != -1 && amt > flow) amt = flow; if (ll pushed = DFS(e.v, T, amt)) { e.flow += pushed; oe.flow -= pushed; return pushed; } } } return 0; } ll MaxFlow(int S, int T) { ll total = 0; while (BFS(S, T)) { fill(pt.begin(), pt.end(), 0); while (ll flow = DFS(S, T)) total += flow; } return total; } }; int board[100][100], up[100][100], down[100][100], n, upnxt, dnnxt; int f(pair pr) { return board[pr.first][pr.second]; } int main() { ios::sync_with_stdio(0);cin.tie(0); int m; cin >> n >> m; while(m--) { int a, b; cin >> a >> b; board[a-1][b-1] = 1; } map>> add, sub; for(int i=0; i

코드 #3088