题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3669
第一道LCT!
主要是看这个博客理解学LCT板子:https://blog.csdn.net/yxuanwkeith/article/details/50991326
关于这道题,又看了看这个博客:https://blog.csdn.net/clove_unique/article/details/51317842
然后努力抄写了半天,成功AC!
代码中 的地方是我还有点不太理解的地方,先写着看吧。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=200005,maxm=1e5+5,inf=0x3f3f3f3f;
int n,m,ans,fa[maxn],mx[maxn],pre[maxn],val[maxn],c[maxn][3];
bool rev[maxn];
struct L{int u,v,a,b;}line[maxm];
int rd()
{
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
bool cmp(L x,L y){return x.a<y.a;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void pushup(int x)
{
mx[x]=x;
if(val[mx[x]]<val[mx[c[x][0]]]) mx[x]=mx[c[x][0]];
if(val[mx[x]]<val[mx[c[x][1]]]) mx[x]=mx[c[x][1]];
}
bool isroot(int x){return c[pre[x]][0]!=x && c[pre[x]][1]!=x;}
void reverse(int x)
{
if(rev[x])
{
rev[c[x][0]]^=1; rev[c[x][1]]^=1;
swap(c[x][0],c[x][1]);
rev[x]=0;
}
}
void rotate(int x)
{
int y=pre[x],z=pre[y],d=(c[y][1]==x);
if(!isroot(y))c[z][c[z][1]==y]=x;
pre[x]=z; pre[y]=x;
c[y][d]=c[x][!d]; pre[c[y][d]]=y; c[x][!d]=y;
pushup(y); pushup(x);
}
void splay(int x)
{
int sta[maxn],top;
sta[top=1]=x;
for(int p=x;!isroot(p);p=pre[p]) sta[++top]=pre[p];
for(;top;top--) reverse(sta[top]);
for(;!isroot(x);rotate(x))
{
int y=pre[x],z=pre[y];
if(isroot(y))continue;
((c[y][0]==x)^(c[z][0]==y))?rotate(x):rotate(y);
}
pushup(x);
}
void access(int x)
{
for(int t=0;x;c[x][1]=t,t=x,x=pre[x]) splay(x);//1:原树中在x下方的不要
}
void makeroot(int x)
{
access(x); splay(x); rev[x]^=1;
}
void link(int x,int y)//把 x 连到y
{
makeroot(x); pre[x]=y;
}
void query(int x,int y)
{
makeroot(x); access(y); splay(y);
}
void cut(int x,int y)//砍断 u , v 的边
{
query(x,y);
pre[x]=0; c[y][0]=0;////
}
int main()
{
n=rd(); m=rd();
for(int i=1;i<=m;i++){line[i].u=rd(); line[i].v=rd(); line[i].a=rd(); line[i].b=rd();}
for(int i=1;i<=n;i++)fa[i]=i;
sort(line+1,line+m+1,cmp);
ans=inf;
for(int i=1;i<=m;i++)
{
int u=line[i].u, v=line[i].v, a=line[i].a, b=line[i].b;
val[i+n]=b;
if(find(u)==find(v))
{
query(u,v);////
int vmx=mx[v];
if(val[i+n]<=val[vmx])
{
cut(vmx,line[vmx-n].u); cut(vmx,line[vmx-n].v);////(顺序?)
link(i+n,u); link(i+n,v);
}
}
else
{
fa[find(u)]=find(v);
// fa[fa[u]]=v;//皆可
link(i+n,u); link(i+n,v);////
}
if(find(1)==find(n))
{
query(1,n);////
ans=min(ans,val[mx[n]]+a);
}
}
printf("%d",(ans==inf?-1:ans));
return 0;
}
转载于:https://www.cnblogs.com/Zinn/p/9194876.html