算法题：口袋的天空

问题描述

小玉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小玉想摘下那样美的几朵云，做成棉花糖。

给你云朵的个数 N，再给你 M 个关系，表示哪些云朵可以连在一起。

现在小玉要把所有云朵连成 K 个棉花糖，一个棉花糖最少要用掉一朵云，小玉想知道他怎么连，花费的代价最小。

输入格式

第一行有三个数 N,M,K。

接下来 M 行每行三个数 X,Y,L，表示 X 云和 Y 云可以通过 L 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 K 个棉花糖，请输出 No Answer。

样例

输入

3 1 2
1 2 1

输出

1

数据范围

1≤N≤10^{3，1≤M≤10}4，1≤K≤10，1≤X,Y≤N，0≤L<10^4。

解决方案

思路

Prim

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


const int N = 1e4 + 5;
int n, m, k;

int vis[N];
int dis[N];

vector<pair<int, int>> g[N];        //下标:连接点 first:被连接的点 second:距离

int main() {

    cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int x, y, l;
        cin >> x >> y >> l;
        g[x].push_back({y, l});
        g[y].push_back({x, l});
    }

    // 小顶堆 first:点与生成树的距离 second:点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, 1});

    int count = 0;
    int sum = 0;

    while (!q.empty() && count < n) {
        auto [w, x] = q.top();
        q.pop();

        if (vis[x]) continue;
        vis[x] = 1;

        ++count;
        sum += w;

        for (auto [y, v]: g[x]) {
            if (dis[y] == 0 || dis[y] > v) {
                dis[y] = v;
                q.push({v, y});
            }
        }
    }

    if (count >= k)
        cout << sum << endl;
    else
        cout << "No Answer" << endl;

    return 0;
}