题目
题目链接
题目大意
给你n个点,m条边,要生成k个最小生成树
题解
刚开始想的就是kruskal,但是没理解串成k串棉花糖。也就是至少生成k个最小生成树。
生成一个n个点的树需要n-1条边,然后生成k个最小生成树那就至少需要n-k条边。
所以我们如果想要连出k棵树,就需要连n-k条边。
题目要求用n朵云连出k个棉花糖。
因为每个棉花糖都是连通的,
那么每个棉花糖就相当于是一棵树。
就是说要用n个节点连出k棵树。
也就是说要用n-k条边连出k棵树。
也就是说要花费连出n-k条边的代价。
既然一定要花费连出n-k条边的代价,
那么当然要选择代价最小的边连起来。
所以给每条可以连的边按代价从小到大排个序,
然后连n-k条边造k个最小生成树就可以了。
如果给的关系数m小于需要连的边数(n-k),是一定连不出k个树来的,因为m个关系只能连m条边。
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define x first
#define y second
#define endl '\n'
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m, k;
struct node{
int x, y, w;
bool operator< (const node &a) const{
return w < a.w;
}
}a[N];
int p[N];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void solve()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) p[i] = i;
ll res = 0, cnt = 0;
for(int i = 1; i <= m; i++){
int x, y, w;
cin >> x >> y >> w;
a[i] = {x, y, w};
}
sort(a + 1, a + m + 1);
for(int i = 1; i <= m; i++){
int x = a[i].x, y = a[i].y, w = a[i].w;
int fx = find(x), fy = find(y);
if(fx != fy){
p[fy] = fx;
res += w;
cnt++;
}
if(cnt >= n - k){
cout << res << endl;
return;
}
}
cout << "No Answer\n";
}
int main()
{
// IOS;
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}