失踪人口回归。
LCT一直是小C的弱项,特别是这种维护链的信息的,写挂了就会调代码调到心态爆炸。
不过还好这一次的模板练习没有出现太多的意外。
Description
Input
Output
按顺序对应输入文件中每一项k=1的任务,你需要输出一个数字和一个回车/换行符。该数字表示:你寻找到的水管路径中所有管道全都完成准备工作所需要的时间(当然要求最短)。
Sample Input
4 4 3
1 2 2
2 3 3
3 4 2
1 4 2
1 1 4
2 1 4
1 1 4
Sample Output
2
3
HINT
N ≤ 100000
M ≤ 1000000
Q ≤ 100000
任何时候我们考虑的水管网络都是连通的,即从任一结点A必有至少一条水管路径通往任一结点B。
Solution
很容易看出题目要求我们维护无向图的最小生成树,查询两点树上路径最大权值,并支持删边操作。
删边不好处理,而且题目没有要求我们在线,我们很容易想到倒过来做,把删边改为加边。
于是用hash判断删去了哪些边(注意hash可能会撞),对删去所有边之后的图做最小生成树。
这样就是LCT维护最小生成树的裸题了。
对于每条新加入的边,查找两端点之间路径最大权值,如果小于那个权值,就删去那条边,并加入这条边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define l(a) son[a][0]
#define r(a) son[a][1]
#define nrt(a) (l(fa[a])==a || r(fa[a])==a)
#define MM 1000005
#define MN 100005
#define mod 10000007
using namespace std;
struct meg1{int x,y,z;}a[MM];
struct meg2{int g,x,y,z,pos;}b[MN];
struct edge{int nex,to,wt,pos;}e[MN<<];
struct dmp{dmp *nex; int x,y,val;}*mp[mod];
int son[MN][],fa[MN],tfa[MN],tson[MN],tg[MN],mx[MN];
int hr[MN],hua[MN],pin;
int n,m,p; inline int read()
{
int n=,f=; char c=getchar();
while (c<'' || c>'') {if(c=='-')f=-; c=getchar();}
while (c>='' && c<='') {n=n*+c-''; c=getchar();}
return n*f;
} void revs(int x) {tg[x]^=; swap(l(x),r(x)); swap(tfa[x],tson[x]);}
void down(int x) {if (tg[x]) {revs(l(x)); revs(r(x)); tg[x]=;}}
int L(int x) {down(x); return l(x)?L(l(x)):x;}
void aldown(int x) {if (nrt(x)) aldown(fa[x]); down(x);}
void upd(int &x,int y) {if (a[y].z>a[x].z) x=y;}
void update(int x) {mx[x]=; upd(mx[x],tfa[x]); upd(mx[x],tson[x]); upd(mx[x],mx[l(x)]); upd(mx[x],mx[r(x)]);}
void rotate(int x)
{
register int y,z,l,r;
y=fa[x]; z=fa[y]; l=r(y)==x; r=l^;
if (nrt(y)) son[z][r(z)==y]=x;
fa[y]=x; fa[x]=z; fa[son[x][r]]=y;
son[y][l]=son[x][r]; son[x][r]=y;
update(y);
}
void splay(int x)
{
aldown(x);
register int y,z;
for (;nrt(x);rotate(x))
{y=fa[x]; if (nrt(y)) z=fa[y],rotate(r(z)==y^r(y)==x?x:y);}
update(x);
}
void access(int x)
{
for (int i=;x;x=fa[i=x])
{
splay(x); tson[x]=tfa[L(i)];
r(x)=i; update(x);
}
} int getmx(int x,int y)
{
access(x); splay(x); revs(x);
access(y); splay(y); return mx[y];
}
void link(int x,int y,int z)
{
access(x); splay(x);
access(y); splay(y); revs(y);
fa[y]=x; r(x)=y; tfa[y]=tson[x]=z;
update(y); update(x);
}
void cut(int x,int y)
{
access(x); splay(x); revs(x);
access(y); splay(y);
l(y)=fa[l(y)]=; tson[x]=tfa[y]=;
update(x); update(y);
} inline void ins(int x,int y,int z,int w)
{
e[++pin]=(edge){hr[x],y,z,w}; hr[x]=pin;
e[++pin]=(edge){hr[y],x,z,w}; hr[y]=pin;
}
void dfs(int x,int fat)
{
fa[x]=fat;
for (register int i=hr[x];i;i=e[i].nex)
if (e[i].to!=fat) mx[e[i].to]=tfa[e[i].to]=e[i].pos,dfs(e[i].to,x);
}
inline bool gather(int x,int y)
{
if (x==y) return false;
hua[x]=y; return true;
}
int getf(int x) {return hua[x]?hua[x]=getf(hua[x]):x;}
bool cmp(const meg1& a,const meg1& b) {return a.z<b.z;} int seamp(int h,int x,int y)
{
for (dmp* q=mp[h];q;q=q->nex) if (q->x==x && q->y==y) return q->val;
return ;
}
void insmp(int h,int x,int y,int z)
{
dmp* q=new(dmp);
q->nex=mp[h]; q->x=x; q->y=y; q->val=z; mp[h]=q;
}
int geth(int x,int y) {return (1LL*x*+y)%mod;} int main()
{
register int i,lt;
n=read(); m=read(); p=read();
for (i=;i<=m;++i)
{
a[i].x=read(); a[i].y=read(); a[i].z=read();
if (a[i].x>a[i].y) swap(a[i].x,a[i].y);
}
for (i=;i<=p;++i)
{
b[i].g=read(); b[i].x=read(); b[i].y=read();
if (b[i].x>b[i].y) swap(b[i].x,b[i].y);
if (b[i].g==) insmp(geth(b[i].x,b[i].y),b[i].x,b[i].y,i);
}
sort(a+,a+m+,cmp);
for (i=;i<=m;++i)
{
if (lt=seamp(geth(a[i].x,a[i].y),a[i].x,a[i].y)) {b[lt].pos=i; continue;}
if (gather(getf(a[i].x),getf(a[i].y))) ins(a[i].x,a[i].y,a[i].z,i);
}
dfs(,);
for (i=p;i;--i)
{
if (b[i].g==) b[i].z=a[getmx(b[i].x,b[i].y)].z;
else if (b[i].g==) {if (a[b[i].pos].z<a[lt=getmx(b[i].x,b[i].y)].z) cut(a[lt].x,a[lt].y),link(b[i].x,b[i].y,b[i].pos);}
}
for (i=;i<=p;++i) if (b[i].g==) printf("%d\n",b[i].z);
}
Last Word
由于link和cut部分可能有点难以理解,LCT一直是令小C头疼的算法之一,但是小C还是成功把模板默出来了。
然后迷之RE,并且发现树上部分节点的关系违背了伦理道德。调完hash之后,结果发现是在找最左边的节点的节点时忘记down操作了。
果然LCT在维护信息时,考虑哪里需要update,哪里需要down,顺序是什么是最烦的。
不得不说,D-map真的好用。