Loading... 市政府“惠民工程”的目标是在全市的**n**个居民点间架设煤气管道(不一定要求直接相连,只需通过管道可达即可)。实际上,最多可架设 **n(n-1)/2** 条管道,但要连通 **n** 个居民点,只需架设 **n-1** 条管道。 现在,请你编写程序来计算完成该惠民工程所需的最低成本。 ### 输入格式 输入包含多组测试数据。 每组数据的第一行包含两个整数 **n** 和 **m**,分别表示居民点数量和评估的管道数量。 接下来的 **m** 行,每行包含三个整数 **a**, **b**, 和 **c**,表示居民点 **a** 和 **b** 之间架设管道所需的成本 **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; } ``` 最后修改:2023 年 09 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏