P1195 口袋的天空

时间:2021-11-14 23:21:41

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:
 
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 口袋的天空的更多相关文章

  1. 洛谷P1195 口袋的天空

    口袋的天空 327通过 749提交 题目提供者该用户不存在 标签云端 难度普及+/提高 时空限制1s / 128MB 提交  讨论  题解 最新讨论更多讨论 暂时没有讨论 题目背景 小杉坐在教室里,透 ...

  2. 洛谷 P1195 口袋的天空

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

  3. 【洛谷】【最小生成树】P1195 口袋的天空

    [题目背景:] 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空. 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖. [题目描述:] 给你云朵的个数N,再给你M个关系,表示哪些 ...

  4. 【luogu P1195 口袋的天空】 题解

    题目链接:https://www.luogu.org/problemnew/show/P1195 嗯~我是被题目背景吸引到才做的,想吃棉花糖啦! 话说回来,这道题其实很容易就能想明白,k棵最小生成树. ...

  5. 洛谷 P1195 口袋的天空(最小生成树)

    嗯... 题目链接:https://www.luogu.org/problemnew/show/P1195 思路: 首先可以判断这道题是用最小生成树来做的,然后在将其合并时用ans记录一下它的总消耗, ...

  6. luogu P1195 口袋的天空

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

  7. P1195 口袋的天空 洛谷

    https://www.luogu.org/problem/show?pid=1195 题目背景 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空. 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美 ...

  8. 洛谷P1195口袋的天空

    传送门啦 一个裸的最小生成树,输出 $ No Answer $ 的情况只有 $ k < n $ 的时候. 开始令 $ num =n $ ,如果 $ num = k $ ,直接输出 $ 0 $ , ...

  9. VIJOS-P1234 口袋的天空

    洛谷 P1195 口袋的天空 https://www.luogu.org/problemnew/show/P1195 JDOJ 1374: VIJOS-P1234 口袋的天空 https://neoo ...

随机推荐

  1. 用springMVC构建restful程序,接收以及返回json数据格式

    主要参考文章:http://kingxss.iteye.com/blog/1487745和http://blog.csdn.net/greensurfer/article/details/192962 ...

  2. 【Java每日一题】20161208

    package Dec2016; import java.util.List; public class Ques1208 { public static void add(List<? ext ...

  3. 网络&amp&semi;热恋NSURLConnection代理及GET¥POST请求

    1.NSURLConnection代理下载设置在本地的身骑着白马MP3 - (void)viewDidLoad { [super viewDidLoad]; // Do any additional ...

  4. &lbrack;翻译&rsqb;创建ASP&period;NET WebApi RESTful 服务(9)

    一旦成功的发布API后,使用者将依赖于你所提供的服务.但是变更总是无法避免的,因此谨慎的制定ASP.NET Web API的版本策略就变得非常重要.一般来说,新的功能需要无缝的接入,有时新老版本需要并 ...

  5. 解决ThinkPHP开启APP&lowbar;DEBUG&equals;&gt&semi;false时报错的问题

    最近用ThinkPHP开发一个项目,本地开发测试完成上传到服务器后,第一次打开正常,再刷新页面时就出现 “页面调试错误,无法找开页面,请重试”的错误,我就郁闷啦,明明本地设置define('APP_D ...

  6. S3C2440 之SPI

    概述: S3C2440有两个串行外设SPI接口,SPI具有全双工通信 SPI方框图 SPI操作: 通过使用SPI接口,S3C2440可以与外部器件同时发送.接收8位数据.当SPI接口为主机时,可以通过 ...

  7. java面向对象(四)之重写、重载

    重载 定义 重载:在一个类中,存在多个方法拥有相同的名字,但在名字相同的同时,必须有不同的参数,这就是重载. 编译器会根据实际情况挑选出正确的方法,如果编译器找不到匹配的参数或者找出多个可能的匹配就会 ...

  8. JavaScript系列----作用域链和闭包

    1.作用域链 1.1.什么是作用域 谈起作用域链,我们就不得不从作用域开始谈起.因为所谓的作用域链就是由多个作用域组成的.那么, 什么是作用域呢? 1.1.1作用域是一个函数在执行时期的执行环境. 每 ...

  9. python基础---面向对象的概念

    1.面向对象 什么是面向过程?? 将一个复杂单位问题一步步小化,最终只需要完成一个人小的功能就可以了 比如:将大象放进冰箱要几步? 一共三步:打开冰箱,把大象塞进入,关门就可以了 优点:复杂度降低了, ...

  10. Python 爬虫二 requests模块

    requests模块 Requests模块 get方法请求 整体演示一下: import requests response = requests.get("https://www.baid ...