题目链接:https://www.luogu.org/problemnew/show/P1195

嗯~我是被题目背景吸引到才做的,想吃棉花糖啦!

话说回来,这道题其实很容易就能想明白,k棵最小生成树。

我们用kruskal的思想,每次连接最小代价的边。假设一开始有n棵树,那么我们每次连接两朵云彩就会减少一棵树。

我们设cnt为生成树的数量,每次连接就会是cnt-1-1-1-1....直到cnt == k,就好啦~

 #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = ; int n,m,k,fa[maxn],cnt,ans = ; int find(int x)
{
return fa[x] == x?x:fa[x] = find(fa[x]);
} struct edge{
int u,v,w;
}e[maxn]; int cmp(edge a,edge b)
{
return a.w<b.w;
} int main()
{
scanf("%d%d%d",&n,&m,&k); for(int i = ; i <= n; i++)
{
fa[i] = i;
} for(int i = ; i <= m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[i].u = x;
e[i].v = y;
e[i].w = z;
}
cnt = n;
sort(e+,e++m,cmp); for(int i = ; i <= m; i++)
{
if(cnt <= k) break; int x = find(e[i].u);
int y = find(e[i].v);
if(x!=y)
{
fa[x] = y;
ans += e[i].w;
cnt--;
} } if(cnt == k)
{
printf("%d",ans);
return ;
}
else
{
printf("No Answer");
return ;
}
}

最新文章

  1. 笔记:Binder通信机制
  2. Azure Queue Storage 基本用法 -- Azure Storage 之 Queue
  3. Linux2.6内核进程调度系列--scheduler_tick()函数3.更新普通进程的时间片
  4. NLP概述
  5. Win 8.1 下 安装 SQL2005
  6. AVAudioRecorder、AVAudioPlayer录音及播放
  7. 小白偶遇Sublime Text 3
  8. AC自动机——多模式串匹配的算法思想
  9. JqMobi学习
  10. BigDecimal-解决商业计算
  11. JavaWeb学习之JDBC API中常用的接口和类
  12. and,or
  13. Spring Data Jpa接口简介
  14. MapServer Tutorial——MapServer7.2.1教程学习(大纲)
  15. xcode9 报错 “Swift Language Version” (SWIFT_VERSION) build setting must be set to a supported value for targets which use Swift
  16. Fiddler怎么可以抓取https的请求包
  17. mybatis源码解析5---SqlSession解析
  18. Cracking The Coding Interview 9.7
  19. 去7JAVA
  20. 【Android病毒分析报告】- 手机支付毒王“银行悍匪”的前世今生

热门文章

  1. Zookeeper概念学习系列之zookeeper是什么?
  2. centos7 中文乱码问题解决方法
  3. TOJ 2861 Octal Fractions
  4. IAR使用技巧 之 快捷键批量更换指定字符(以及Keil的全局替换功能)
  5. Tomcat 启动很慢?
  6. keepalive学习之软件设计
  7. 命令行编译java项目
  8. 修改Linux时区的2种办法
  9. 如何查询日志文件中的所有ip,正则表达式
  10. jQuery plugin: Tablesorter 2.0