P1195 - 口袋的天空

Solost

2023 年 04 月 24 日

204 次浏览

1 条评论

1595字数

题目题解

## 题目

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F24%2Fimage.png)

## 题目链接

[链接](https://www.luogu.com.cn/problem/P1195)

## 题目大意

给你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条边。

```cpp
#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;
}
```

最后修改：2023 年 04 月 24 日