链接1到n号,目的是去除其中一条边使得1到n无法链接并打印“Fail”,当前者无法实现时则去除其中一条边使得链接1到n的边的权重和最大化 输入格式: 第一行包含两个整数n和m,n为关系网中的人数。 编号从1至n。m表示有m个边。(3 <n= 30, 3<=m <=1000) 接下来有m行。每行包含三个整数A、B和C,意思是A和B之间存在边,C为权重。 输出格式: 输出最少权重和。如果生成树被破坏,就打印“Fail”。 给我一个c++的示例代码
时间: 2024-03-10 11:44:37 浏览: 136
以下是一个使用 Kruskal 算法求解最小生成树的示例代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 35, M = 1010;
struct Edge {
int a, b, w;
bool operator<(const Edge& e) const {
return w < e.w;
}
} edges[M];
int p[N];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
sort(edges, edges + m);
for (int i = 1; i <= n; i++) p[i] = i;
int cnt = 0, res = 0;
for (int i = 0; i < m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
cnt++;
res += w;
if (cnt == n - 1) break;
}
}
if (cnt < n - 1) puts("Fail");
else cout << res << endl;
return 0;
}
```
该代码使用结构体存储边信息,使用 Kruskal 算法求解最小生成树,并输出最小生成树的权值和或 "Fail"。
阅读全文