怎么自己注册网站,制作网页的模板的网站,崇明建设镇乡镇府网站,北京城乡建设集团有限公司官网口袋的天空
题目背景
小杉坐在教室里#xff0c;透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里#xff0c;看起来很漂亮#xff0c;小杉想摘下那样美的几朵云#xff0c;做成棉花糖。
题目描述
给你云朵的个数 N N N#xff0c;再给你 M M M 个关系…口袋的天空
题目背景
小杉坐在教室里透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里看起来很漂亮小杉想摘下那样美的几朵云做成棉花糖。
题目描述
给你云朵的个数 N N N再给你 M M M 个关系表示哪些云朵可以连在一起。
现在小杉要把所有云朵连成 K K K 个棉花糖一个棉花糖最少要用掉一朵云小杉想知道他怎么连花费的代价最小。
输入格式
第一行有三个数 N , M , K N,M,K N,M,K。
接下来 M M M 行每行三个数 X , Y , L X,Y,L X,Y,L表示 X X X 云和 Y Y Y 云可以通过 L L L 的代价连在一起。
输出格式
对每组数据输出一行仅有一个整数表示最小的代价。
如果怎么连都连不出 K K K 个棉花糖请输出 No Answer。
样例 #1
样例输入 #1
3 1 2
1 2 1样例输出 #1
1提示
对于 30 % 30\% 30% 的数据 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100 1 ≤ M ≤ 1 0 3 1\le M \le 10^3 1≤M≤103
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 3 1 \le N \le 10^3 1≤N≤103 1 ≤ M ≤ 1 0 4 1 \le M \le 10^4 1≤M≤104 1 ≤ K ≤ 10 1 \le K \le 10 1≤K≤10 1 ≤ X , Y ≤ N 1 \le X,Y \le N 1≤X,Y≤N 0 ≤ L 1 0 4 0 \le L10^4 0≤L104。
分析
若将每个云朵看作图中的节点则可理解为花费最小代价连成k个树可以使用Kruskal做最小生成树若每连接一个点使cnt若n-cntk则说明已联通退出即可
代码
#includebits/stdc.h
using namespace std;
const int maxn10005;
int n,m,k;
int p[maxn];
int ans;
struct Edge{int u,v,w;}edges[maxn];
struct cmp { bool operator () (const Edge a,const Edge b) { return a.wb.w; }
};
int find(int x) { p[x]x?x:p[x]find(p[x]); }
void init(int n) { for(int i1;in;i) p[i]i; }
int main()
{cinnmk;for(int i1;im;i) { cinedges[i].uedges[i].vedges[i].w; }init(n);int cnt0;sort(edges1,edges1m,cmp());for(int i1;im;i){int xfind(edges[i].u),yfind(edges[i].v);if(find(edges[i].u)!find(edges[i].v)) {p[find(edges[i].u)]find(edges[i].v);ansedges[i].w;cnt;}if (kn-cnt){coutans;break;}}if (k!n-cnt)coutNo Answer;return 0;
}分析
struct Edge{int u,v,w;}edges[maxn];
struct cmp { bool operator () (const Edge a,const Edge b) { return a.wb.w; }
};利用结构体存图需要按边权排序自定义一个函数 for(int i1;im;i){int xfind(edges[i].u),yfind(edges[i].v);if(find(edges[i].u)!find(edges[i].v)) {p[find(edges[i].u)]find(edges[i].v);ansedges[i].w;cnt;}if (kn-cnt){coutans;break;}}并查集维护需要判断是否已完成
