分析

从大到小考虑每个点

记录一个连通块中选了选了几个

如果选的小于siz则直接选否则不选

代码

#include<bits/stdc++.h>
using namespace std;
struct node {
int x,y,z;
};
node d[];
int n,m,fa[],siz[],use[];
inline int sf(int x){return fa[x]==x?x:fa[x]=sf(fa[x]);}
inline bool cmp(const node x,const node y){return x.z>y.z;}
int main(){
int i,j,k,Ans=;
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)fa[i]=i,siz[i]=;
for(i=;i<=n;i++)scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z);
sort(d+,d+n+,cmp);
for(i=;i<=n;i++){
int x=d[i].x,y=d[i].y;
if(sf(x)!=sf(y)){
siz[sf(y)]+=siz[sf(x)];
use[sf(y)]+=use[sf(x)];
fa[sf(x)]=sf(y);
if(use[sf(x)]<siz[sf(x)])use[sf(x)]++,Ans+=d[i].z;
}else {
if(use[sf(x)]<siz[sf(x)])use[sf(x)]++,Ans+=d[i].z;
}
}
cout<<Ans;
return ;
}

最新文章

  1. 虚拟机体验之 KVM 篇
  2. Oracle数据库自动增长列的实现过程
  3. 【解决】若要使用报表生成器,必须在此计算机上安装 .Net Framework 3.5
  4. Shell--用户配置
  5. iPad开发--iPad中modal的更多用法
  6. webservice 学习笔记
  7. vim不用鼠标复制粘贴
  8. linux运维的认知及RHEL7 Unix/Linux 系统 介绍和安装
  9. Android模拟器配置
  10. android 项目学习随笔三(Fragment )
  11. 加载网络映射盘中的assembly失败的处理办法
  12. hdoj 2473 Junk-Mail Filter【并查集节点的删除】
  13. VC获取精确时间的做法
  14. Computational Network Toolkit (CNTK) 是微软出品的开源深度学习工具包
  15. JS---控制键盘事件
  16. Python可迭代对象中的添加和删除(add,append,pop,remove,insert)
  17. Impala系列:Impala查询优化
  18. 11 vs2015 连接oracle 11g 数据库及相关问题
  19. jmeter配置脚本录制进行抓包并快速分析、定位接口问题
  20. json 数据在textarea中显示的时候,切换 beauty和ugly模式

热门文章

  1. js字符串、数组处理方法、以及一些常用js方法
  2. 剑指Offer编程题(Java实现)——二维数组中的查找
  3. 如何配置属于自己的Git账户
  4. SpringMVC Controller单例和多例(转)
  5. addEventListener 的三个参数
  6. PREPARE - 创建一个准备好的查询
  7. VS2012在解决方案资源管理器显示解决方案名称
  8. tomcat的跳转与日志
  9. Memcache--02 源码安装nginx,php
  10. 2019 Multi-University Training Contest 3 Find the answer (离散化+二分+树状数组)