当前位置：首页 > 洛谷 > 洛谷P1195题解析：Kruskal算法构建K个连通分量的优化解法

洛谷P1195题解析：Kruskal算法构建K个连通分量的优化解法

3个月前 (09-13)

一、题目解读

洛谷P1195题要求处理一个图论问题：给定N朵云和M条边，每条边连接两朵云并附带代价，需通过添加边将云朵分组，使得最终形成K个连通分量，且总代价最小。若无法恰好形成K个连通分量，则输出“No Answer”。题目核心在于利用最小生成树的思想，在限定连通分量数量下求解最优解。

二、解题思路

采用Kruskal算法与并查集的结合。首先对所有边按代价升序排序，随后通过并查集维护连通分量。遍历每条边时，若合并后能减少连通分量数量且不超出K的限制，则加入该边并累加代价。关键在于利用路径压缩优化并查集查找，降低时间复杂度。

三、解题步骤

1. 输入云朵数N、边数M、目标连通分量数K。

2. 初始化并查集数组（每个云朵自成连通分量）。

3. 读取所有边存入结构体中，按代价排序。

4. 循环遍历边：

○ 若当前连通分量数已≤K，跳出循环。

○ 通过find()函数查找两云朵的根节点，若不同则合并，更新总代价及连通分量数。

5. 检查最终连通分量数是否等于K，输出总代价或“No Answer”。

四、代码及注释

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 定义边的结构体
struct Edge {
    int x, y, l; // x和y表示云朵编号，l表示连接代价
    bool operator<(const Edge& other) const {
        return l < other.l; // 按代价从小到大排序
    }
};

vector<Edge> edges; // 存储所有边
vector<int> parent; // 并查集数组

// 并查集查找根节点
int find(int x) {
    if (parent[x]!= x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    
    // 初始化并查集
    parent.resize(N+1);
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
    }
    
    // 读取所有边
    edges.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].l;
    }
    
    // 按边权从小到大排序
    sort(edges.begin(), edges.end());
    
    int totalCost = 0;
    int connectedComponents = N; // 初始时每个云朵自成一个连通分量
    
    // Kruskal算法构建最小生成森林
    for (const auto& e : edges) {
        if (connectedComponents <= K) break; // 已经形成K个连通分量
        
        int rootX = find(e.x);
        int rootY = find(e.y);
        
        if (rootX!= rootY) { // 如果不在同一个连通分量
            parent[rootY] = rootX; // 合并
            totalCost += e.l;
            connectedComponents--; // 连通分量减少1
        }
    }
    
    // 检查是否能形成K个棉花糖
    if (connectedComponents == K) {
        cout << totalCost << endl;
    } else {
        cout << "No Answer" << endl;
    }
    
    return 0;
}