Untitled
unknown
plain_text
a year ago
4.4 kB
3
Indexable
#include <iostream> #include <vector> #include <queue> struct edge_type { int64_t flow{ 0 }; int64_t capacity; edge_type(int64_t capacity): capacity(capacity) {} }; struct vertex_type { uint32_t to; uint32_t edge; vertex_type(uint32_t to, uint32_t edge): to(to), edge(edge) {} }; struct graph_type { uint32_t s; uint32_t t; std::vector<std::vector<vertex_type>> vertexes; std::vector<edge_type> edges; std::vector<int> level; std::vector<uint32_t> path; std::vector<uint32_t> queue; void add_edge(uint32_t from, uint32_t to, int64_t capacity) { uint32_t direct_edge = edges.size(); edges.emplace_back(capacity); vertexes[from].emplace_back(to, direct_edge); uint32_t reverse_edge = edges.size(); edges.emplace_back(0); vertexes[to].emplace_back(from, reverse_edge); } bool bfs() { uint32_t r = 0; uint32_t l = 0; queue[r] = s; ++r; std::fill(level.begin(), level.end(), -1); level[s] = 0; while (l < r) { uint32_t v = queue[l]; ++l; for (const auto& vertex : vertexes[v]) { const auto& edge = edges[vertex.edge]; if (level[vertex.to] == -1 && (edge.capacity - edge.flow) > 0) { queue[r] = vertex.to; ++r; level[vertex.to] = level[v] + 1; } } } return level[t] != -1; } int64_t push_flow (uint32_t v, int64_t flow) { if (flow == 0 || v == t) { return flow; } uint32_t vertex_count = vertexes[v].size(); for (auto& i = path[v]; i < vertex_count; ++i) { const auto& vertex = vertexes[v][i]; auto& edge = edges[vertex.edge]; if (level[v] + 1 != level[vertex.to] || (edge.capacity - edge.flow) < 1) { continue; } int64_t pushed_flow = push_flow(vertex.to, std::min(flow, edge.capacity - edge.flow)); if (pushed_flow == 0) { continue; } edge.flow += pushed_flow; edges[vertex.edge ^ 1].flow -= pushed_flow; return pushed_flow; } return 0; } int64_t dinic() { int64_t flow = 0; while (true) { if (!bfs()) { break; } int64_t pushed_flow = 0; std::fill(path.begin(), path.end(), 0); do { pushed_flow = push_flow(s, INT64_MAX); if (pushed_flow > 0) { flow += pushed_flow; } } while (pushed_flow != 0); } return flow; } }; // void stdio_init(graph_type& graph) { // int n, m; // std::cin >> n; // std::cin >> m; // graph.level.resize(n, 0); // graph.queue.resize(n, 0); // graph.path.resize(n, 0); // graph.s = 0; // graph.t = n - 1; // graph.vertexes.resize(n, std::vector<vertex_type>()); // int from, to, capacity; // for (int i = 0; i < m; ++i) { // std::cin >> from; // std::cin >> to; // std::cin >> capacity; // graph.add_edge(from - 1, to - 1, capacity); // } // } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, k; std::cin >> n; std::cin >> k; int vertex_count = 2*n + 2; graph_type graph; graph.level.resize(vertex_count, 0); graph.queue.resize(vertex_count, 0); graph.path.resize(vertex_count, 0); graph.s = 0; graph.t = vertex_count - 1; graph.vertexes.resize(vertex_count, std::vector<vertex_type>()); int64_t capacity; for (int i = 0; i < n; ++i) { std::cin >> capacity; graph.add_edge(0, i + 1, capacity); } uint32_t vertex_number = n + 1; uint32_t t = vertex_count - 1; for (; vertex_number < t; ++vertex_number) { std::cin >> capacity; graph.add_edge(vertex_number, t, capacity); } uint32_t from, to; for (int i = 0; i < k; ++i) { std::cin >> from; std::cin >> to; to += n; graph.add_edge(from, to, 1000000); } std::cout << graph.dinic() << "\n"; return 0; }
Editor is loading...
Leave a Comment