Editorial for Vương quốc hạnh phúc
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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;
}
Comments