Hướng dẫn giải của Vương quốc hạnh phúc
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Nhận xét: Trong trường hợp ~k=1~, bài toán này trở thành bài toán Tìm cây khung có trọng số nhỏ nhất. Từ đây, ta dễ dàng nhìn ra rằng, trong lúc xây dựng cạnh, số lượng thành phần liên thông giảm ~1~ sau mỗi lần thêm cạnh mới, và chi phí sẽ luôn là chi phí nhỏ nhất trong suốt quá trình thêm cạnh.
Vì vậy thuật toán của ta sẽ là: lúc đầu ta để số thành phần liên thông là ~n~, với mỗi lần thêm cạnh nối hai TPLT khác nhau, ta giảm số TPLT đi ~1~, lặp lại cho tới khi số TPLT = ~k~.
Code tham khảo:
#include <bits/stdc++.h>
#define reu(i, a, b) for(ll i = a; i <= b; i++)
#define red(i, a, b) for(ll i = a; i >= b; i--)
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define de(x) #x << ": " << x
#define pb push_back
#define faster ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
//╰(*°▽°*)╯
using namespace std;
typedef int64_t ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vll;
const ll base = 87;
const ll mod = 1001;
const ll N = 1e6 + 2;
const ll oo = 1e14 + 7;
ll testcase = 1;
ll n, m, k;
ll par[N], sz[N];
vector<pair<ll, ii>> edge;
ll GetPar(ll u) {
if (u != par[u]) par[u] = GetPar(par[u]);
return par[u];
}
void join(ll u, ll v) {
u = GetPar(u);
v = GetPar(v);
if (sz[u] > sz[v]) {
sz[u] += sz[v];
par[v] = u;
} else {
sz[v] += sz[u],
par[u] = v;
}
}
void solve() {
cin >> n >> m >> k;
reu(i, 1, n) par[i] = i, sz[i] = 1;
reu(i, 1, m) {
ll u, v, c;
cin >> u >> v >> c;
edge.pb({c, {u, v}});
}
sort(all(edge));
ll res = 0;
for(ll i = 0; i < edge.size() && n > k; ++i) {
ll u = edge[i].S.F, v = edge[i].S.S;
ll c = edge[i].F;
if (GetPar(u) != GetPar(v)) {
join(u, v);
res += c;
--n;
}
}
cout << res;
}
int main()
{
faster;
#define name "nhap"
while(testcase--) {
solve();
}
return 0;
}
Bình luận