#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; } }; /* i in: i*2-3: i out: i*2-2 */ int in(int i) { return i <= 2 ? i : i*2-3; } int out(int i) { return i <= 2 ? i : i*2-2; } int main() { ios::sync_with_stdio(0);cin.tie(0); int n, m; cin >> n >> m; Dinic dinic(n*2); while(m--) { int a, b; cin >> a >> b; dinic.AddEdge(out(a), in(b), 1); dinic.AddEdge(out(b), in(a), 1); } for(int i=3; i<=n; i++) { dinic.AddEdge(in(i), out(i), 1); } cout << dinic.MaxFlow(1, 2); }

코드 #2993