P1195 口袋的天空
题目背景
小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。
有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。
题目描述
给你云朵的个数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
说明
厦门一中YMS原创
题解:
n个点 m条边 连成k个树的最小代价
若k为1 则连成一棵MST 跑一次kruskal n-1次连边
若 k为2 为最后的图必须为 两颗MST n-2次连边
同理 连成k个mst 进行 n-k次连边
若进行者n-k次操作中 没有了边 (即cpp中的 i<m) 直接输出 No Answer
AC代码:
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+;
struct node{
int u,v,w;
bool operator < (const node &a) const{
return w<a.w;
}
}e[N];
int n,m,k,ans,fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+,e+m+);
int js=;
for(int i=,fx,fy;n-k>=js;i++){
if(i>m){
puts("No Answer");
return ;
}
fx=find(e[i].u);fy=find(e[i].v);
if(fx!=fy){
fa[fy]=fx;
js++;
ans+=e[i].w;
}
}
printf("%d",ans);
return ;
}
P1195 口袋的天空的更多相关文章
-
洛谷P1195 口袋的天空
口袋的天空 327通过 749提交 题目提供者该用户不存在 标签云端 难度普及+/提高 时空限制1s / 128MB 提交 讨论 题解 最新讨论更多讨论 暂时没有讨论 题目背景 小杉坐在教室里,透 ...
-
洛谷 P1195 口袋的天空
题目背景 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空. 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖. 题目描述 给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在 ...
-
【洛谷】【最小生成树】P1195 口袋的天空
[题目背景:] 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空. 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖. [题目描述:] 给你云朵的个数N,再给你M个关系,表示哪些 ...
-
【luogu P1195 口袋的天空】 题解
题目链接:https://www.luogu.org/problemnew/show/P1195 嗯~我是被题目背景吸引到才做的,想吃棉花糖啦! 话说回来,这道题其实很容易就能想明白,k棵最小生成树. ...
-
洛谷 P1195 口袋的天空(最小生成树)
嗯... 题目链接:https://www.luogu.org/problemnew/show/P1195 思路: 首先可以判断这道题是用最小生成树来做的,然后在将其合并时用ans记录一下它的总消耗, ...
-
luogu P1195 口袋的天空
题目背景 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空. 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖. 题目描述 给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在 ...
-
P1195 口袋的天空 洛谷
https://www.luogu.org/problem/show?pid=1195 题目背景 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空. 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美 ...
-
洛谷P1195口袋的天空
传送门啦 一个裸的最小生成树,输出 $ No Answer $ 的情况只有 $ k < n $ 的时候. 开始令 $ num =n $ ,如果 $ num = k $ ,直接输出 $ 0 $ , ...
-
VIJOS-P1234 口袋的天空
洛谷 P1195 口袋的天空 https://www.luogu.org/problemnew/show/P1195 JDOJ 1374: VIJOS-P1234 口袋的天空 https://neoo ...
随机推荐
-
用springMVC构建restful程序,接收以及返回json数据格式
主要参考文章:http://kingxss.iteye.com/blog/1487745和http://blog.csdn.net/greensurfer/article/details/192962 ...
-
【Java每日一题】20161208
package Dec2016; import java.util.List; public class Ques1208 { public static void add(List<? ext ...
-
网络&;热恋NSURLConnection代理及GET¥POST请求
1.NSURLConnection代理下载设置在本地的身骑着白马MP3 - (void)viewDidLoad { [super viewDidLoad]; // Do any additional ...
-
[翻译]创建ASP.NET WebApi RESTful 服务(9)
一旦成功的发布API后,使用者将依赖于你所提供的服务.但是变更总是无法避免的,因此谨慎的制定ASP.NET Web API的版本策略就变得非常重要.一般来说,新的功能需要无缝的接入,有时新老版本需要并 ...
-
解决ThinkPHP开启APP_DEBUG=>;false时报错的问题
最近用ThinkPHP开发一个项目,本地开发测试完成上传到服务器后,第一次打开正常,再刷新页面时就出现 “页面调试错误,无法找开页面,请重试”的错误,我就郁闷啦,明明本地设置define('APP_D ...
-
S3C2440 之SPI
概述: S3C2440有两个串行外设SPI接口,SPI具有全双工通信 SPI方框图 SPI操作: 通过使用SPI接口,S3C2440可以与外部器件同时发送.接收8位数据.当SPI接口为主机时,可以通过 ...
-
java面向对象(四)之重写、重载
重载 定义 重载:在一个类中,存在多个方法拥有相同的名字,但在名字相同的同时,必须有不同的参数,这就是重载. 编译器会根据实际情况挑选出正确的方法,如果编译器找不到匹配的参数或者找出多个可能的匹配就会 ...
-
JavaScript系列----作用域链和闭包
1.作用域链 1.1.什么是作用域 谈起作用域链,我们就不得不从作用域开始谈起.因为所谓的作用域链就是由多个作用域组成的.那么, 什么是作用域呢? 1.1.1作用域是一个函数在执行时期的执行环境. 每 ...
-
python基础---面向对象的概念
1.面向对象 什么是面向过程?? 将一个复杂单位问题一步步小化,最终只需要完成一个人小的功能就可以了 比如:将大象放进冰箱要几步? 一共三步:打开冰箱,把大象塞进入,关门就可以了 优点:复杂度降低了, ...
-
Python 爬虫二 requests模块
requests模块 Requests模块 get方法请求 整体演示一下: import requests response = requests.get("https://www.baid ...