2025年洛谷 P1195 口袋的天空

洛谷 P1195 口袋的天空题目背景 小杉坐在教室里 透过口袋一样的窗户看口袋一样的天空 有很多云飘在那里 看起来很漂亮 小杉想摘下那样美的几朵云 做成棉花糖 题目描述 给你云朵的个数 N 再给你 M 个关系 表示哪些云朵可以连在一起 现在小杉要把所有云朵连成 K 个棉花糖

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

题目背景

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

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

题目描述

给你云朵的个数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; } 

 

小讯
上一篇 2025-02-10 22:10
下一篇 2025-03-14 18:48

相关推荐

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