解题:WC 2006 水管局长
2024-09-03 22:34:29
初见LCT,动态最小生成树+链上查询max,具体做法是把边转换成点(LCT只能维护点)
时光倒流,先把最后剩的连起来。然后查询就看链上最大值,修改看看链上最大值是否大于当前边,如果是就断开原来的改成当前边
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct a{int x,y,c;}mst[N];
struct b{int x,y,typ;}qry[N];
map<pair<int,int>,int> mmp;
int fth[N],son[N][],val[N];
int maxx[N],stk[N],outp[N];
bool brk[N],rev[N];
int n,m,T,p,t1,t2,cnt,top;
bool cmp(a xx,a yy)
{
return xx.c<yy.c;
}
void Pushup(int nde)
{
maxx[nde]=val[nde];
int &mx=maxx[nde],&mx1=maxx[son[nde][]],&mx2=maxx[son[nde][]];
if(mst[mx1].c>mst[mx].c) mx=mx1; if(mst[mx2].c>mst[mx].c) mx=mx2;
}
void Release(int nde)
{
if(rev[nde])
{
int &lson=son[nde][],&rson=son[nde][];
rev[lson]^=,rev[rson]^=,rev[nde]^=;
swap(lson,rson);
}
}
bool Nottop(int nde)
{
int fa=fth[nde];
return son[fa][]==nde||son[fa][]==nde;
}
void Rotate(int nde)
{
int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][];
if(Nottop(fa)) son[gr][son[gr][]==fa]=nde;
fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa;
son[fa][isl^]=son[nde][isl],son[nde][isl]=fa;
Pushup(fa),Pushup(nde);
}
void Splay(int nde)
{
stk[top=]=nde;
for(int i=nde;Nottop(i);i=fth[i])
stk[++top]=fth[i];
while(top) Release(stk[top--]);
while(Nottop(nde))
{
int fa=fth[nde],gr=fth[fa];
if(Nottop(fa))
Rotate(((son[fa][]==nde)==(son[gr][]==fa))?fa:nde);
Rotate(nde);
}
}
void Access(int nde)
{
int lst=,mem=nde;
while(nde)
{
Splay(nde),son[nde][]=lst;
Pushup(nde),lst=nde,nde=fth[nde];
}
Splay(mem);
}
void Turnroot(int nde)
{
Access(nde),rev[nde]^=;
}
int Getroot(int nde)
{
Access(nde);
while(son[nde][])
nde=son[nde][];
return nde;
}
void Split(int x,int y)
{
Turnroot(x),Access(y);
}
int Query(int x,int y)
{
Split(x,y);
return maxx[y];
}
void Link(int x,int y)
{
Turnroot(x);
if(Getroot(y)!=x) fth[x]=y;
}
void Cut(int x,int y)
{
Turnroot(x);
if(Getroot(y)==x&&fth[x]==y&&!son[x][])
son[y][]=fth[x]=;
}
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t1,&t2,&mst[i].c);
if(t1>t2) swap(t1,t2); mst[i].x=t1,mst[i].y=t2;
}
sort(mst+,mst++m,cmp);
for(int i=;i<=m;i++)
mmp[make_pair(mst[i].x,mst[i].y)]=i;
for(int i=;i<=T;i++)
{
scanf("%d%d%d",&qry[i].typ,&t1,&t2);
if(t1>t2) swap(t1,t2); qry[i].x=t1,qry[i].y=t2;
if(qry[i].typ==) brk[mmp[make_pair(t1,t2)]]=true;
}
for(int i=;i<=m;i++)
val[i+n]=maxx[i+n]=i;
for(int i=;i<=m&&cnt<n-;i++)
if(!brk[i])
{
int tx=mst[i].x,ty=mst[i].y;
Turnroot(tx);
if(Getroot(ty)!=tx)
cnt++,Link(tx,i+n),Link(ty,i+n);
}
for(int i=T;i;i--)
if(qry[i].typ==)
outp[++p]=mst[Query(qry[i].x,qry[i].y)].c;
else
{
int tx=qry[i].x,ty=qry[i].y;
int id=mmp[make_pair(tx,ty)],me=Query(tx,ty);
if(mst[id].c<mst[me].c)
{
Cut(mst[me].x,me+n),Cut(mst[me].y,me+n);
Link(tx,id+n),Link(ty,id+n);
}
}
while(p)
printf("%d\n",outp[p--]);
return ;
}
最新文章
- [luogu2964][USACO09NOV][硬币的游戏A Coin Game] (博弈+动态规划)
- Spring系列之Spring常用注解总结
- java笔记--关于线程同步(7种同步方式)
- 再谈vertical-align与line-height
- ios蓝牙开发(四)app作为外设被连接的实现-转发
- jQuery MD5加密实现代码
- akka cluster sharding source code 学习 (2/5) handle off
- linux安全
- 关于delegate, category和subclass
- Oracle PL/SQL 事物处理 银行转账
- CI框架篇之辅助函数篇--基本(1)
- River Hopscotch(二分)
- 对数的操作 开始我的JAVA历程
- AMQP协议学习
- Java集合框架(一)—— Collection、Iterator和Foreach的用法
- 【IOS 开发】Object-C 运算符
- ve2.0 v-for循环报错的解决方案
- temp-重庆银行
- Python大法之告别脚本小子系列—信息资产收集类脚本编写(下)
- 实例详解Java中如何对方法进行调用