目录

题目

P5633 最小度限制生成树

算法标签: 最小生成树, k r u s k a l kruskal kruskal重构树, 贪心

思路

题目大意就是构建最小生成树, 但是要求点 s s s的 d e g deg deg必须是 k k k

  1. 首先先将与 s s s连接的边先删除, 将与 s s s连接的边标记为特殊边
  2. 然后对剩余的部分进行 k r u s k a l kruskal kruskal算法, 这样就会产生很多连通块, 在合并两个连通块的时候将特殊边权更大的集合合并到特殊边更小的集合, 这是个贪心的策略, 保证最后连接 s s s的边权尽可能小
  3. 然后在合并两个集合的过程中, 如果发现存在特殊边, 那么计算如果使用普通边, 会节约多少的值
  4. 然后枚举所有的特殊边, 因为要求 d e g = k deg = k deg=k, 计算在合并连通块过程中使用了多少条特殊边
  5. 然后对 k − d e g k- deg k−deg条特殊边从小到大排序, 选出最优的 k − d e g k - deg k−deg条边

算法时间复杂度 O ( m log ⁡ m ) O(m \log m) O(mlogm)

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 50010, M = 500010, INF = 0x3f3f3f3f;

int n, m, s, k, idx;

struct Edge {
   
    int u, v, w;

    bool operator<(const Edge &e) const {
   
        return w < e.w;
    }
} edges[M << 1];
int p[N], val[N];

void add(int u, int v, int w) {
   
    edges[idx++] = {
   u, v, w};
}

int find(int x) {
   
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
   
    for (int i = 1; i <= n; ++i) p[i] = i;
    sort(edges, edges + idx);

    int ans = 0;
    vector<int> vec;

    // 构建最小生成树
    for (int i = 0; i < idx; ++i) {
   
        auto [u, v, w] = edges[i];
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;

        // 总是将较大val的集合合并到较小val的集合
        if (val[fu] > val[fv]) swap(fu, fv);
        p[fv] = fu;
        ans += w;
        if (val[fv] < INF) vec.push_back(val[fv] - w);
    }

    // 计算必须选择的特殊边
    int deg = 0;
    for (int i = 1; i <= n; ++i) {
   
        if (p[i] != i || i == s) continue;
        if (val[i] >= INF) {
   
            cout << "Impossible" << "\n";
            exit(0);
        }
        deg++;
        ans += val[i];
    }

    // 检查可行性
    if (deg > k || deg + vec.size() < k) {
   
        cout << "Impossible" << "\n";
        exit(0);
    }

    sort(vec.begin(), vec.end());
    for (int i = 0; i < k - deg; ++i) ans += vec[i];

    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(val, 0x3f, sizeof val);
    cin >> n >> m >> s >> k;

    // 处理输入
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        if (u == s) val[v] = min(val[v], w);
        else if (v == s) val[u] = min(val[u], w);
        else add(u, v, w);
    }

    // 特殊情况处理：如果k=0但s有边
    if (k == 0) {
   
        for (int i = 1; i <= n; ++i) {
   
            if (val[i] < INF) {
   
                cout << "Impossible" << "\n";
                return 0;
            }
        }
    }

    int ans = kruskal();
    cout << ans << "\n";
    return 0;
}