Hướng giải của Kết nối nguồn điện
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải
Gom tất cả nguồn điện thành 1 thành phần liên thông lớn ban đầu (DSU) rồi chạy Kruskal.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
long long w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
struct DSU {
vector<int> parent;
DSU(int n) {
parent.resize(n + 1);
for (int i = 0; i <= n; i++) parent[i] = i;
}
int find(int v) {
if (v == parent[v]) return v;
return parent[v] = find(parent[v]);
}
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
parent[b] = a;
return true;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, s;
if (!(cin >> n >> m >> s)) return 0;
DSU dsu(n);
vector<int> stations(s);
for (int i = 0; i < s; i++) {
cin >> stations[i];
}
// Connect all stations to node 0 with weight 0
for (int i = 1; i < s; i++) {
dsu.unite(stations[0], stations[i]);
}
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
sort(edges.begin(), edges.end());
long long total_cost = 0;
int components = n - s; // initially S stations are already in 1 component
int needed = n - 1; // if we include virtual node, but here we can just use DSU components check
// We want to count how many edges we add to connect the remaining nodes.
// If n=1 and s=1, it is 0
for (auto& e : edges) {
if (dsu.unite(e.u, e.v)) {
total_cost += e.w;
components--;
}
}
// Check if everything is connected to the stations component
bool ok = true;
int root = dsu.find(stations[0]);
for (int i = 1; i <= n; i++) {
if (dsu.find(i) != root) {
ok = false;
break;
}
}
if (ok) {
cout << total_cost << "\n";
} else {
cout << -1 << "\n";
}
return 0;
}
Nhận xét