[BZOJ2753]滑雪与时间胶囊
2024-09-28 16:40:23
第一问直接把可以走的边连起来bfs一遍即可
第二问可以用类似kruskal的方法,只不过排序的依据应该变为第一关键字为终点高度(从大到小),第二关键字为边权(从小到大),只排序可以走的边
因为同样高度的点之间的边是双向边,所以同一个高度的所有点构成了一个强连通分量,考虑终点在这个强连通分量的所有边,要么是在这个强连通分量中,要么是从更高处过来的边,我们处理这两种边都可以把它们当成无向边,也就是直接套用kruskal
#include<stdio.h> #include<algorithm> using namespace std; struct edge{ int x,y,v; edge(int a=0,int b=0,int c=0){x=a;y=b;v=c;} }e[2000010]; int hi[100010],h[100010],to[2000010],nex[2000010],q[2000010],fa[100010],M; bool v[100010]; int get(int x){return(fa[x]==x)?x:(fa[x]=get(fa[x]));} void add(int a,int b,int c){ M++; to[M]=b; nex[M]=h[a]; h[a]=M; e[M]=edge(a,b,c); } bool cmp(edge a,edge b){return(hi[a.y]==hi[b.y])?(a.v<b.v):(hi[a.y]>hi[b.y]);} int main(){ int n,m,i,x,y,z,head,tail; long long ans; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",hi+i); for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); if(hi[x]>=hi[y])add(x,y,z); if(hi[x]<=hi[y])add(y,x,z); } head=tail=1; q[1]=1; while(head<=tail){ x=q[head]; head++; v[x]=1; for(i=h[x];i;i=nex[i]){ if(!v[to[i]]){ tail++; q[tail]=to[i]; } } } x=0; for(i=1;i<=n;i++)x+=v[i]; printf("%d\n",x); for(i=1;i<=n;i++)fa[i]=i; sort(e+1,e+M+1,cmp); ans=0; for(i=1;i<=M;i++){ if(!v[e[i].x]||!v[e[i].y])continue; x=get(e[i].x); y=get(e[i].y); if(x!=y){ fa[x]=y; ans+=e[i].v; } } printf("%lld",ans); }
最新文章
- 解决服务器SID引起虚拟机不能加入AD域用户,无法远程登录的问题
- How to use groovy script on jenkins
- ffmpeg去logo<;转>;
- hadoop 集群部署ganglia 监控服务与nagios 报警服务
- 第12章 使用Samba或NFS实现文件共享
- 浅谈github页面域名绑定
- 简明CSS属性:定位
- Spring自动扫描
- jQuery怎样判断按钮是否被选中
- .4-Vue源码之数据劫持(2)
- RHCE6.4 rpm 安装gcc
- Aspose.Words的Merge Field
- Git系列:第七篇-Maven项目下提交时忽略不必要的文件或文件夹
- 发送http请求的方法
- [转]抛弃jQuery,使用原生JavaScript
- kali蓝牙连接
- Spring 监听
- Tomcat学习总结(13)—— Tomcat常用参数配置说明
- Linux默认日志含义
- open-falcon之alarm、sender、links说明.md
热门文章
- CSS中的text-shadow。
- php设定错误和异常处理可使用的函数
- Spring学习--集合属性
- js删除一个父元素下面的所有子元素
- Python基础(4)_集合、布尔类型
- php连接mysql报错——Fatal error: Call to undefined function mysql_connect() in
- CDLinux 自动休眠功能的关闭方法
- 破解wifi时遇到rtl8187 - [phy1]SIOCSIFFLAGS: Name not unique on network
- doxygen使用
- js 触发LinkButton点击事件,执行后台方法