Luogu P1195 口袋的天空

发表于 | 更新于 | 阅读次数：

题目背景

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

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

题目描述

给你云朵的个数 $N$ ，再给你 $M$ 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 $K$ 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入输出格式

输入格式：

每组测试数据的第一行有三个数 $N,M,K(1≤N≤1000,1≤M≤10000,1≤K≤10)$ 。

接下来M个数每行三个数X,Y,L表示X云和Y云可以通过L的代价连在一起。$(1\le X,Y\le N,0\le L\le 10000)$

$30%$ 的数据 $N\le 100,M\le 1000$

输出格式：

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 $K$ 个棉花糖，请输出' $No Answer$ '。

输入输出样例

输入样例#1：

1
2
3 1 2
1 2 1

输出样例#1：

1
1

题解

怎么会有这么裸的模板题。。。还是绿题。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int n,m,k,father[1005],t,ans;
struct Edge{
	int x,y,dis;
}edge[10005];
bool cmp(Edge x,Edge y){
	return x.dis<y.dis;
}
int find(int x){
	if(father[x]!=x)father[x]=find(father[x]);
	return father[x];
}
void unionn(int x,int y,int dis){
	int a=find(x),b=find(y);
	father[a]=b;
	t--;
	ans+=dis;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	if(m<n-k){
		printf("No Answer");
		return 0;
	}
	t=n;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].dis);
	sort(edge+1,edge+m+1,cmp);
	for(int i=1;i<=n;i++)father[i]=i;
	for(int i=1;i<=m;i++){
		if(find(edge[i].x)!=find(edge[i].y))unionn(edge[i].x,edge[i].y,edge[i].dis);
		if(t==k)break;
	}
	printf("%d",ans);
	return 0;
}