洛谷 P2121 拆地毯

题目背景
还记得 NOIP 2011 提高组 Day1 中的铺地毯吗?时光飞逝,光阴荏苒,三年过去了。组织者精心准备的颁奖典礼早已结束,留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

题目描述
会场上有 n 个关键区域,不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示,其中 u 和 v 为地毯连接的两个关键区域编号,w 为这条地毯的美丽度。

由于颁奖典礼已经结束,铺过的地毯不得不拆除。为了贯彻勤俭节约的原则,组织者被要求只能保留 K 条地毯,且保留的地毯构成的图中,任意可互相到达的两点间只能有一种方式互相到达。换言之,组织者要求新图中不能有环。现在组织者求助你,想请你帮忙算出这 K 条地毯的美丽度之和最大为多少。

输入格式
第一行包含三个正整数 n、m、K。

接下来 m 行中每行包含三个正整数 u、v、w。

输出格式
只包含一个正整数,表示这 K 条地毯的美丽度之和的最大值。

最小生成树板子题

#include <cstdio>
#include <iostream>
#include <algorithm>
#define inf 2000000000
#define int long long 
using namespace std;
const int M=200004;
const int N=5005;
int n,m,k;
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(){
   
	int tot=0,ans=0;
	for(int i=1;i<=m;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==k){
   
			printf("%lld",ans);
			return ;
		}
	}
}
main(){
   
	n=read();m=read();k=read(); 
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)bian[i].x=read(),bian[i].y=read(),bian[i].z=read();
	sort(bian+1,bian+m+1); 
	kruskal();
	return 0;
}

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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-02 10:46
韶关学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-11-29 17:43
北京大学_2023
点赞 评论 收藏
转发
头像
2022-12-01 12:52
广州商学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议