P1234口袋的天空

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

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

描述

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

样例输入1[复制]

3 1 2
1 2 1

样例输出1[复制]

1

限制

每个测试点1s

提示

样例2:
Input:
3 1 1
1 2 1

Output:
No Answer

【分析】这个最小生成树题很有意思,他要求K个最小生成树,因为共有n朵云并且一朵云就可以构成一个棉花糖,所以不用云构造花费为0,那么就要留出k-1朵云单独作为一个棉花糖,即将剩下的n-(k-1)朵云构造 成一棵最小生成树,即当加入的边数=n-(k-1)-1时构造完成。此时构造的为最小生成树,构造这个棵树花费最小,其他花费为0,所以这样就以最小的花 费构造出了k个棉花糖;
算法以并查集优化的kruscal来构造即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include<functional>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int N=; struct Edg
{
int v,u;int w;
}edg[*+];
bool cmp(Edg g,Edg h)
{
return g.w<h.w;
}
int n,m,k,cnt=,maxn;
int parent[N];
void init()
{
for(int i=;i<n;i++)parent[i]=i;
}
void Build()
{
int u,v,w;
for(int i=;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
edg[i].u=u;edg[i].v=v;edg[i].w=w;
}
if(n<k){printf("No Answer\n");exit();}
sort(edg,edg+m,cmp);
}
int Find(int x) {
if(parent[x] != x) parent[x] = Find(parent[x]);
return parent[x];
}//查找并返回节点x所属集合的根节点
void Union(int x,int y) {
x = Find(x);
y = Find(y);
if(x == y) return;
parent[y] = x;
}//将两个不同集合的元素进行合并
void Kruskal()
{
int sum=;
int num=;
int u,v;
for(int i=;i<m;i++)
{
u=edg[i].u;v=edg[i].v;
if(Find(u)!=Find(v))
{
sum+=edg[i].w; num++;
Union(u,v);
}
if(num>=n-(k-)-){
printf("%d\n",sum);
break;
}
}
if(num<n-(k-)-)printf("No Answer\n");
}
int main() {
scanf("%d%d%d",&n,&m,&k);
init();
Build();
Kruskal();
return ;
}

最新文章

  1. 【转】hive优化之--控制hive任务中的map数和reduce数
  2. Section 1.4 Mother&#39;s Milk
  3. mysql主从复制 主从配置(windows系统上)
  4. JS将搜索的关键字高亮显示实现代码
  5. 在Mybatis-spring中由于默认Autowired导致不能配置多个数据源的问题分析及解决
  6. Qt之模型/视图(自定义按钮)(重绘QStyleOptionButton)
  7. [Linux] rlwrap - 解决Linux下sqlplus退格、上翻键乱码问题
  8. 【C疯狂的教材】(四)C语言分支语句
  9. Android Studio 错误集
  10. php设计模式2
  11. Java多线程之定时任务(Timer)
  12. 【转】关于提示can&#39;t load package &#39;xxx.bpl.&#39; 错误问题的解决方法
  13. 基于VS Code创建Spring Boot项目开发REST API(一)
  14. 《DSP using MATLAB》Problem 5.5
  15. 关联Left Outer Join的第一条记录
  16. HDU 5517 【二维树状数组///三维偏序问题】
  17. C# 微信小程序获取openid sessionkey
  18. windows server 2008 域控安装
  19. [转载]php设计模式之单例、多例设计模式
  20. iptables数据包、连接标记模块MARK/CONNMARK的使用(打标签)

热门文章

  1. 【题解】JSOI2010满汉全席
  2. [洛谷P2197]nim游戏
  3. fzu 2246(ac 自动机)
  4. pmap用法小计
  5. java的哈希遍历 hashmap
  6. C#弱引用
  7. x:Class, x:Key
  8. offset--BUG
  9. Spring学习--基于 XML 的配置声明切面
  10. 解决tomcat不支持中文路径的问题