Untitled
unknown
plain_text
a year ago
3.6 kB
5
Indexable
#include <deque> #include <ios> #include <iostream> #include <queue> #include <vector> #include <unordered_set> struct edge_type { int64_t capacity; int64_t cost; int64_t flow{0}; edge_type(int64_t capacity, int64_t cost) : capacity(capacity), cost(cost) {} }; struct vertex_type { uint32_t to; uint32_t edge; vertex_type(uint32_t to, uint32_t edge) : to(to), edge(edge) {} vertex_type() : to(UINT32_MAX), edge(UINT32_MAX) {} }; struct graph_type { uint32_t s; uint32_t t; std::vector<std::vector<vertex_type>> vertexes; std::vector<edge_type> edges; std::vector<uint32_t> distance; std::vector<vertex_type> parent; std::vector<uint8_t> id; void add_edge(uint32_t from, uint32_t to, int64_t capacity, int64_t cost) { // std::cout << "from: " << from << ", to: " << to << ", capacity: " << // capacity << ", cost: " << cost << "\n"; uint32_t direct_edge = edges.size(); edges.emplace_back(capacity, cost); vertexes[from].emplace_back(to, direct_edge); uint32_t reverse_edge = edges.size(); edges.emplace_back(0, -cost); vertexes[to].emplace_back(from, reverse_edge); } int64_t min_cost() { int64_t min_cost = 0; std::deque<uint32_t> queue; while (true) { std::fill(distance.begin(), distance.end(), INT32_MAX); std::fill(parent.begin(), parent.end(), vertex_type()); std::fill(id.begin(), id.end(), 0); distance[0] = 0; queue.push_back(0); while (!queue.empty()) { uint32_t v = queue.front(); queue.pop_front(); id[v] = 2; for (const auto &vertex : vertexes[v]) { const auto &edge = edges[vertex.edge]; if (edge.flow < edge.capacity && distance[vertex.to] > (distance[v] + edge.cost)) { distance[vertex.to] = distance[v] + edge.cost; if (id[vertex.to] == 0) { queue.push_back(vertex.to); } else if (id[vertex.to] == 2) { queue.push_front(vertex.to); } id[vertex.to] = 1; parent[vertex.to].to = v; parent[vertex.to].edge = vertex.edge; } } } int64_t flow = INT64_MAX; if (distance[t] == INT32_MAX) { break; } for (uint32_t v = t; v != 0; v = parent[v].to) { const auto &edge = edges[parent[v].edge]; flow = std::min(flow, edge.capacity - edge.flow); } for (uint32_t v = t; v != 0; v = parent[v].to) { auto &edge = edges[parent[v].edge]; auto &reverse_edge = edges[parent[v].edge + 1]; edge.flow += flow; reverse_edge.flow -= flow; min_cost += (edge.flow == 1 ? edge.cost : 0); } } return min_cost; } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int boats_count, persons_count; std::cin >> boats_count; std::cin >> persons_count; size_t vertex_count = persons_count + boats_count + 2; graph_type graph; graph.vertexes.resize(vertex_count); graph.distance.resize(vertex_count); graph.id.resize(vertex_count); graph.parent.resize(vertex_count, vertex_type()); graph.t = vertex_count - 1; int val; for (int i = 0; i < boats_count; ++i) { std::cin >> val; graph.add_edge(1 + i + persons_count, graph.t, val, 1); } int boat; for (int i = 0; i < persons_count; ++i) { graph.add_edge(0, i + 1, 1, 0); std::cin >> val; for (int j = 0; j < val; ++j) { std::cin >> boat; graph.add_edge(i + 1, persons_count + boat, 1, 0); } } std::cout << graph.min_cost() << "\n"; return 0; }
Editor is loading...
Leave a Comment