洛谷 P1195 口袋的天空

自用。

题目传送门：口袋的天空 - 洛谷

题解：Inori_333

参考题解：题解 P1195 【口袋的天空】 - 洛谷专栏

/*P1195 口袋的天空https://www.luogu.com.cn/problem/P11952024/11/03  submit:inori333
*/#include <iostream>
#include <algorithm>
using namespace std;int n, m, k; // n个点，m条边，连成k棵树，就是说要用n个节点连出k棵树。也就是说要用n - k条边连出k棵树。 
int ans = 0;//最终的最小生成树耗费
int cnt = 0;//已经连通的边数struct edge{int u, v, w;//u,v是边的两个端点，w是边的权值
} e[200005];//边的数组int f[200005];//并查集状态数组bool cmp(edge a,edge b){return a.w < b.w;
}//重载比较函数int find(int x){if(f[x]==x)return x;elsereturn f[x] = find(f[x]);
}//并查集查找int main(){cin >> n >> m >> k;// 初始化并查集for (int i = 1; i <= n;i++){f[i] = i;}for (int i = 1; i <= m;i++){cin >> e[i].u >> e[i].v >> e[i].w;}sort(e + 1, e + 1 + m, cmp);// Kruskal算法，共m条边，所以循环m次for (int i = 1; i <= m; i++){if (find(e[i].u) != find(e[i].v)){                                   // 如果两个节点的祖宗不相等，也就是说，不会构成回路f[find(e[i].u)] = find(e[i].v); // 将他们合并成同一个祖宗ans += e[i].w;                  // 加上这条边的权值cnt++;                          // 边数加一}if(cnt==n-k)break;}if (cnt==n-k)cout << ans;elsecout<<"No Answer";return 0;
}