市政府“惠民工程”的目标是在全市的n个居民点间架设煤气管道(不一定要求直接相连,只需通过管道可达即可)。实际上,最多可架设 n(n-1)/2 条管道,但要连通 n 个居民点,只需架设 n-1 条管道。

现在,请你编写程序来计算完成该惠民工程所需的最低成本。

输入格式

输入包含多组测试数据。

每组数据的第一行包含两个整数 nm,分别表示居民点数量和评估的管道数量。

接下来的 m 行,每行包含三个整数 a, b, 和 c,表示居民点 ab 之间架设管道所需的成本 c

居民点的编号范围是 1~n

输出格式

对于每组数据,输出一行结果,表示完成全市管道畅通所需的最低成本。

如果提供的数据不足以保证管道畅通,则输出 ?

数据范围

  • 2 ≤ n ≤ 100
  • 1 ≤ m ≤ n(n-1)/2
  • 1 ≤ a, b ≤ n
  • 1 ≤ c ≤ 100

每个输入最多包含 100 组数据。

输入样例

3 3
1 2 1
1 3 2
2 3 4
3 1
2 3 2

输出样例

3
?

题目分析

最小生成树

  • Kruskal 不能以节点是否已被连接作为成树条件(非连通图)

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
using PII = pair <int,int>;
const int N = 1e2 + 10;

int n, m, a, b, c;
class UnionFind {
    int p[N];
public:
    UnionFind (int n) {
        for (int i = 1; i <= n; ++i) p[i] = i;
    }
    int find(int i) {
        return p[i] == i ? i : p[i] = find(p[i]);
    }
    void merge(int i, int j) {
        p[find(i)] = find(j);
    }
};
typedef struct {
    int a, b, c;
}edge;
void solve () {
    int ans = 0, cnt = 0;
    UnionFind uf(n);
    vector <edge> edges;
    while(m--) {
        cin >> a >> b >> c;
        edges.push_back({a,b,c});
    }
    sort(edges.begin(),edges.end(),[] (const edge& a, const edge& b) {
        return a.c < b.c;
    });
    for (const auto& i : edges) {
        if (uf.find(i.a) != uf.find(i.b)) {
            ++cnt;
            uf.merge(i.a,i.b);
            ans += i.c;
        }
    }
    if (cnt >= n - 1) cout << ans << '\n';
    else cout << "?\n";
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> n >> m) solve();
    return 0;
} 
分类: Kruskal

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status