| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1011144 | avi_sri | Training (IOI07_training) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct Edge {
int u, v, cost;
bool paved;
};
vector<Edge> edges;
vector<int> parent, rank;
vector<int> even_cycle_costs;
int find(int u) {
if (parent[u] != u)
parent[u] = find(parent[u]);
return parent[u];
}
void unite(int u, int v) {
int root_u = find(u);
int root_v = find(v);
if (root_u != root_v) {
if (rank[root_u] > rank[root_v]) {
parent[root_v] = root_u;
} else if (rank[root_u] < rank[root_v]) {
parent[root_u] = root_v;
} else {
parent[root_v] = root_u;
rank[root_u]++;
}
}
}
bool has_even_cycle(int n) {
parent.resize(n + 1);
rank.resize(n + 1, 0);
for (int i = 1; i <= n; ++i) {
parent[i] = i;
}
for (const auto& edge : edges) {
if (edge.paved) {
if (find(edge.u) == find(edge.v)) {
return true;
} else {
unite(edge.u, edge.v);
}
}
}
return false;
}
int main() {
int N, M;
cin >> N >> M;
for (int i = 0; i < M; ++i) {
int A, B, C;
cin >> A >> B >> C;
edges.push_back({A, B, C, C == 0});
}
// Check for even cycles in the paved road tree
if (has_even_cycle(N)) {
cout << 0 << endl;
return 0;
}
// Gather all costs of unpaved roads
for (const auto& edge : edges) {
if (!edge.paved) {
even_cycle_costs.push_back(edge.cost);
}
}
// Sort the costs to find the minimum cost to block the roads
sort(even_cycle_costs.begin(), even_cycle_costs.end());
int total_cost = 0;
for (int cost : even_cycle_costs) {
total_cost += cost;
}
cout << total_cost << endl;
return 0;
}