题目背景
小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。
题目描述
给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在一起。
现在小杉要把所有云朵连成K个棉花糖,一个棉花糖最少要用掉一朵云,小杉想知道他怎么连,花费的代价最小。
输入格式
每组测试数据的
第一行有三个数N,M,K(1≤N≤1000,1≤M≤10000,1≤K≤10)
接下来M行每行三个数X,Y,L表示X云和Y云可以通过L的代价连在一起。(1≤X,Y≤N,0≤L<10000)
30%的数据N≤100,M≤1000
输出格式
对每组数据输出一行,仅有一个整数,表示最小的代价。
如果怎么连都连不出K个棉花糖,请输出'No Answer'。
输入输出样例
输入 #1复制
3 1 2 1 2 1
讯享网
输出 #1复制
讯享网1
说明/提示
厦门一中YMS原创
思路:使用最小生成树的kruskal算法。
首先我们需要知道,对于最小生成树的kruskal算法,我们每往生成树中加入一条边,连通块的个数就减一。
比方说一开始N个云朵,每个云朵都是一个独立的云朵群,我们每加入一条边(前提是不会形成环),独立的云朵群的个数就会减一,因为有两个独立的云朵群合并为一个独立的云朵群。
而我们最终需要的独立的云朵群个数为K,也就是棉花糖的个数K。下面分情况讨论:
1. 如果我们一开始的云朵群个数N小于K,那么我们怎么合并也合并不出来K个云朵群。此时输出No Answer。
2. 如果我们在使用kruskal算法加边时,发现无论如何也加不进去N-K条边(N个云朵群加入N-K条边后就变成了K个云朵群),说明无法把N个云朵群合并为K个云朵群,原因是缺乏一些边。那么这个时候输出No Answer。
3. 如果我们在使用kruskal算法加边时,发现可以加入进去N-K条边,那么此时最初的N个云朵群就合并成了K个云朵群,我们加入这N-K条边的代价,就是答案所求的最小的代价。
#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<queue> using namespace std; const int MAXN = 1004; const int INF = ; struct Node{ int id; int cost; Node(int id,int cost){ this->id = id; this->cost = cost; } }; struct Edge{ int u; int v; int w; Edge(int u,int v,int w){ this->u = u; this->v = v; this->w = w; } }; vector<Edge> edges; int father[MAXN]; int cost[MAXN]; vector<Node> group; void initFather(int n){ for(int i=0;i<=n;i++){ father[i] = i; } } int findFather(int x){ int z = x; while(x != father[x]){ x = father[x]; } int temp; while(z != father[z]){ temp = z; z = father[z]; father[temp] = x; } return x; } bool unionFather(int x,int y,int w){ int fx = findFather(x); int fy = findFather(y); if(fx != fy){ father[fy] = fx; cost[fx] += cost[fy] + w; return true; } return false; } bool cmp(const Edge &edge1,const Edge &edge2){ return edge1.w < edge2.w; } bool fatherCmp(const Node &node1, const Node &node2){ return node1.cost < node2.cost; } int kruskal(int n,int k){ int cnt = 0; int result = 0; initFather(n); sort(edges.begin(),edges.end(),cmp); for(int i=0;i<edges.size();i++){ Edge edge = edges[i]; int u = edge.u; int v = edge.v; int w = edge.w; if(unionFather(u,v,w)){ cnt++; result += w; if(cnt == n-k){ return result; } } } return -1; } int main(){ int n,m,k; int x,y,l; cin>>n>>m>>k; while(m--){ cin>>x>>y>>l; edges.push_back(Edge(x,y,l)); } if(n < k){ cout<<"No Answer"<<endl; }else{ int result = kruskal(n,k); if(result == -1){ cout<<"No Answer"<<endl; }else{ cout<<result<<endl; } } return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/133024.html