2025年洛谷 P1195 口袋的天空（最小生成树）题解

科技前沿 • 2025-03-27 21:22 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

题目来源：

https://www.luogu.org/problemnew/show/P1195

题目描述：

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数NN，再给你MM个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成KK个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入输出格式

输入格式：

每组测试数据的

第一行有三个数N,M,K(1 \le N \le 1000,1 \le M \le 10000,1 \le K \le 10)N,M,K(1≤N≤1000,1≤M≤10000,1≤K≤10)

接下来MM个数每行三个数X,Y,LX,Y,L，表示XX云和YY云可以通过LL的代价连在一起。(1 \le X,Y \le N,0 \le L<10000)(1≤X,Y≤N,0≤L<10000)

30\%30%的数据N \le 100,M \le 1000N≤100,M≤1000

讯享网

输出格式：

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出KK个棉花糖，请输出'No Answer'。

输入输出样例

输入样例#1： 复制

3 1 2 1 2 1

讯享网

输出样例#1： 复制

讯享网1

说明

厦门一中YMS原创

解题思路：

题目就是让求最小k个生成树，没有连边的时候是n个联通快，用并查集判断，每连一条边n--，当深k个联通快的时候，就是题目求得了、、、

代码：

#include <iostream> #include <string> #include <cstring> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cmath> #include <cctype> #include <iomanip> const int maxn=1e4+10; using namespace std; struct newt { int from,to,cost; }edge[maxn]; int fa[maxn],n,m,k; int fi(int x) { if(fa[x]==x)return x; return fa[x]=fi(fa[x]); } bool cmp(newt a,newt b) { return a.cost<b.cost; } int main() { int ans=0; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].cost); } sort(edge+1,edge+m+1,cmp); int flag=0; for(int i=1;i<=m;i++) { int f1=fi(edge[i].from),f2=fi(edge[i].to); if(f1!=f2) { n--; ans+=edge[i].cost; fa[f1]=f2; } if(n==k) { flag=1;break; } } if(flag)printf("%d\n",ans); else printf("No Answer\n"); return 0; }

2025年洛谷 P1195 口袋的天空（最小生成树） 题解