Given weighted undirected graph, every vertex has its country "C[v]" and money "V[v]". Let's call vertex "v" "responsible" if there exist at least one edge (v, u, cost) where C[v] == C[u]. Also, you can do this operation infinitely many times: Choose edge (v, u, cost), delete it, and add edge (k, u, cost), where C[u] == C[k] and u != k. After this operation make subtraction V[k] -= cost (of course after this operation V[k] must be >= 0). You need to maximize number of responsible vertices

Edited by author 14.08.2024 13:04