#include using namespace std; using ll = long long; 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, cap); 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; // printf(" pushed %lld: %d -> %d\n", pushed, e.u, e.v); return pushed; } } } return 0; } ll MaxFlow(int S, int T) { ll total = 0; while (BFS(S, T)) { fill(pt.begin(), pt.end(), 0); // printf(" dfs try\n"); while (ll flow = DFS(S, T)) total += flow; } return total; } }; struct edg { int u, v, w; }; int32_t main() { cin.tie(0)->sync_with_stdio(0); int N, M; cin >> N >> M; vector edges; for(int i=0; i> u >> v >> w; edges.push_back({u, v, w}); } sort(edges.begin(), edges.end(), [](auto a, auto b) { return a.w < b.w; }); int ans = 0; for(int i=0; i= edges[i].w) break; // printf(" add edge %d - %d\n", edges[j].u, edges[j].v); dinic.AddEdge(edges[j].u, edges[j].v, 1); } int f = dinic.MaxFlow(edges[i].u, edges[i].v); // printf("at %d - %d, f = %d\n", edges[i].u, edges[i].v, f); ans += f; } cout << ans; }

코드 #4147