天津集团网站建设,南京网站制作设计公司,深圳小程序开发推荐,网站功能模版自用。
题目传送门#xff1a;口袋的天空 - 洛谷
题解#xff1a;Inori_333
参考题解#xff1a;题解 P1195 【口袋的天空】 - 洛谷专栏
/*P1195 口袋的天空https://www.luogu.com.cn/problem/P11952024/11/03 submit:inori333
*/#include iostream
#include 口袋的天空 - 洛谷
题解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(cntn-k)break;}if (cntn-k)cout ans;elsecoutNo Answer;return 0;
}
