洛谷P1195 口袋的天空

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

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

题目描述
给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在一起。

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

输入格式
每组测试数据的

第一行有三个数N,M,K(1 \le N \le 1000,1 \le M \le 10000,1 \le K \le 10)N,M,K(1≤N≤1000,1≤M≤10000,1≤K≤10)

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

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

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

如果怎么连都连不出KK个棉花糖,请输出’No Answer’。

题解:
我们第一个想法,这个东西必然和最小生成树有点关系,他要求k棵树,我们不妨想象求出一棵树,然后给他断开,这题就好简单了
上代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define inf 2000000000
#define For(i) for(int i=1;i<=m;i++)
#define fo(i) for(int i=1;i<=n;i++) 
using namespace std;
const int M=200004;
const int N=5005;
int n,m,k,tot,ans;
int fa[M];
struct NODE{
   
    int x,y,z;
    bool operator <(const NODE &a){
   
    	return this->z < a.z;
	}
}bian[M*2];
inline int read(){
   
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int find(int x){
   
	if(fa[x]==x) return x;
	else return find(fa[x]);
}
inline void kruskal(){
   
    tot=0;ans=0;
	sort(bian+1,bian+m+1);
	fo(i) fa[i]=i;
	For(i){
   
	   if(fa[find(bian[i].x)]!=fa[find(bian[i].y)]){
   
			fa[find(bian[i].x)]=fa[find(bian[i].y)];
			tot++;
			ans=ans+bian[i].z;
		}
		if(tot==n-k){
   
			printf("%d",ans);
			return ;
		}
	}
}
int main(){
   
	n=read();m=read();k=read();
	For(i){
   
		bian[i].x=read();
		bian[i].y=read();
		bian[i].z=read();
	}
	if(k>n){
   
		puts("No Answer");
		exit(0);
	}
	else	kruskal();
	
    return 0; 
} 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议