EZOJ #393加倍的飞机
2024-09-29 15:33:30
分析
从大到小考虑每个点
记录一个连通块中选了选了几个
如果选的小于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 ;
}
最新文章
- 虚拟机体验之 KVM 篇
- Oracle数据库自动增长列的实现过程
- 【解决】若要使用报表生成器,必须在此计算机上安装 .Net Framework 3.5
- Shell--用户配置
- iPad开发--iPad中modal的更多用法
- webservice 学习笔记
- vim不用鼠标复制粘贴
- linux运维的认知及RHEL7 Unix/Linux 系统 介绍和安装
- Android模拟器配置
- android 项目学习随笔三(Fragment )
- 加载网络映射盘中的assembly失败的处理办法
- hdoj 2473 Junk-Mail Filter【并查集节点的删除】
- VC获取精确时间的做法
- Computational Network Toolkit (CNTK) 是微软出品的开源深度学习工具包
- JS---控制键盘事件
- Python可迭代对象中的添加和删除(add,append,pop,remove,insert)
- Impala系列:Impala查询优化
- 11 vs2015 连接oracle 11g 数据库及相关问题
- jmeter配置脚本录制进行抓包并快速分析、定位接口问题
- json 数据在textarea中显示的时候,切换 beauty和ugly模式