COJ 0500 杨老师的路径规划(MST)最小生成树
2024-10-15 23:22:14
杨老师的路径规划(MST) |
难度级别:B; 运行时间限制:1000ms; 运行空间限制:51200KB; 代码长度限制:2000000B |
试题描述
|
为满足同学们需求,杨老师在实验楼4层新建了好多个计算机教室供同学们使用。可是这样的话,由于路径很长,杨老师发现越来越难亲自走到每一个机房看看同学们有没有在玩游戏了。请你现在帮杨老师设计一个程序,给你每个教室间的路径长,设计出一条路线使每两个教室间都能联通且总长度最小,你只需要输出这个最小值即可。(裸MST) |
输入
|
测试用例的第1行给出教室数目N ( < 100 );随后的N(N-1)/2行对应教室间的距离,每行给出三个正整数,分别是两个教室的编号,以及此两教室间的距离(int范围)。为简单起见,教室从1到N编号。
|
输出
|
输出最小的路径总长度。
|
输入示例
|
3
1 2 1 1 3 2 2 3 4 |
输出示例
|
3
|
其他说明
|
n<100
|
动态的最小生成树LCT:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<=1;d++) if(ch[d])
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
struct node{
node*fa,*ch[],*mx;int x;bool rev;
node(){fa=ch[]=ch[]=NULL;mx=this;x=;rev=false;}
void revt(){swap(ch[],ch[]);rev^=;return;}
void update(){mx=this;CH{if(mx->x<ch[d]->mx->x)mx=ch[d]->mx;}return;}
void down(){if(rev){CH{ch[d]->revt();}rev=false;}return;}
}lct[maxn+maxm],*nodecnt;
int parent(node*x,node*&y){return (y=x->fa)?y->ch[]==x?:y->ch[]==x?:-:-;}
void rotate(node*x){
node*y,*z;int d1=parent(x,y),d2=parent(y,z);
if(y->ch[d1]=x->ch[d1^]) y->ch[d1]->fa=y;
y->fa=x;x->fa=z;x->ch[d1^]=y;
if(d2!=-) z->ch[d2]=x;
y->update();return;
}
void pushdown(node*x){
static node*s[maxn];int top=;
for(node*y;;x=y){
s[top++]=x;y=x->fa;
if(!y||(y->ch[]!=x&&y->ch[]!=x)) break;
} while(top--) s[top]->down();return;
}
node*splay(node*x){
pushdown(x);node*y,*z;int d1,d2;
while(true){
if((d1=parent(x,y))<) break;
if((d2=parent(y,z))<){rotate(x);break;}
if(d1==d2) rotate(y),rotate(x);
else rotate(x),rotate(x);
} x->update();return x;
}
node*access(node*x){
node*ret=NULL;
for(;x;x=x->fa) splay(x)->ch[]=ret,(ret=x)->update();
return ret;
}
void makeroot(int x){access(x+lct)->revt();return;}
void link(int x,int y){makeroot(x);splay(x+lct)->fa=lct+y;return;}
void cut(int x,int y){
makeroot(x);node*p=(access(y+lct),splay(y+lct));
p->ch[]=p->ch[]->fa=NULL;p->update();return;
}
node*findtop(int x){
node*t=(access(x+lct),splay(x+lct));while(t->ch[]) t->down(),t=t->ch[];return t;
}
node*query(int x,int y){
makeroot(x);return access(y+lct)->mx;
}
int n,m;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int s[maxm],t[maxm];
void init(){
n=read();m=n*(n-)>>;int ans=;nodecnt=lct+n+;
for(int i=;i<=m;i++){
s[i]=read();t[i]=read();node*q=nodecnt++;q->x=read();int k=q-lct;makeroot(k);
if(findtop(s[i])!=findtop(t[i])){
link(s[i],k);link(t[i],k);ans+=q->x;
}else{
node*p=query(s[i],t[i]);if(p->x<q->x) continue;
ans+=q->x-p->x;int id=p-lct-n;
cut(s[id],p-lct);cut(t[id],p-lct);
link(s[i],k);link(t[i],k);
}
} write(ans);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
静态Kruskal:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+;
struct edge{int x,y,w;}e[maxm];
bool cmp(edge a,edge b){return a.w<b.w;}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n,m,fa[maxn];
int findset(int x){return (fa[x]==x)?x:fa[x]=findset(fa[x]);}
void init(){
n=read();m=n*(n-)>>;
for(int i=;i<=n;i++) fa[i]=i;
int x,y;
for(int i=;i<=m;i++){
x=read();y=read();
e[i]=(edge){x,y,read()};
}
sort(e+,e++m,cmp);
int ans=,cnt=;
for(int i=;i<=m;i++){
int x=findset(e[i].x),y=findset(e[i].y);
if(x!=y){
fa[y]=x;ans+=e[i].w;
if(++cnt==n-) break;
}
} write(ans);
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
最新文章
- WebGIS中等值面展示的相关方案简析
- windows下node环境配置
- sublime下安装ctags
- golang在Windows下Sublime Text开发调试环境的配置
- ios 友盟第三方登录遇到的各种坑。
- iOS定位 (一) 地图定位
- Service解析
- HDOJ(HDU) 2106 decimal system(进制相互转换问题)
- Unity 角色复活和重新开始游戏
- Flunetd 用于统一日志记录层的开源数据收集器
- web前端-----JAVA Script(一)
- bzoj 3207: 花神的嘲讽计划Ⅰ
- springmvc学习之jdk版本,tomcat版本,spring版本
- Python3学习之路~5.1 模块介绍
- java通过反射调用有参数的方法
- 把iPad上的视频推送到大麦盒子去
- 最新Java校招面试题及答案
- Android 性能分析工具 TraceView
- 3.如何在Maven项目中引入自己的jar包
- DIV+CSS:如何编写代码才能更有效率