IV.[NOI2014]魔法森林
前三题都是模板，是为了让我们练手的。
这题才是真正的挑战。
首先，一看这题既不加边也不删边，甚至连树都不是，还是道静态题，并且长得还贼像最小生成树，我就纳闷了，这是LCT？
还真是。
我们可以将边按照\(a\)排序。之后，我们维护一个关于\(b\)权值的动态最小生成树。
具体做法是，建立一个LCT，这个LCT维护的是最大值的下标。之后，按照\(a\)递增的顺序遍历所有的边。如果这条边连接了两块尚未被连接的区域，那不要废话直接连；否则，这肯定构成一个环。我们在LCT中\(split\)出来这个环在当前MST上的部分，并找到这里面的最大值的位置。如果最大值比当前这条边的\(b\)还要大，那么断掉最大值的边并用当前边代替肯定更优。因此我们就这么做。在每加完一条边后，如果当前节点\(1\)和节点\(n\)是连通的，那么\(split(1,n)\)，并将（当前的\(a\)+[\(1-n\)链上的最大值]）与当前答案取\(\min\)。
哦，另外，为了将边权转成点权，我们将每条边视作一个点
核心代码：
for(int i=1;i<=n+m;i++)t[i].val=0,t[i].mx=dsu[i]=i;
for(int i=n+1;i<=n+m;i++)t[i].val=e[i-n].b;
for(int i=1;i<=m;i++){
if(merge(e[i].x,e[i].y))link(e[i].x,n+i),link(n+i,e[i].y);
else{
int pos=split(e[i].x,e[i].y);
if(t[pos].val<e[i].b)continue;
cut(pos,e[pos-n].x),cut(pos,e[pos-n].y);
link(e[i].x,n+i),link(n+i,e[i].y);
}
if(find(1)==find(n))res=min(res,e[i].a+t[split(1,n)].val);
}
应该比较好理解不然我怎么能1A
总代码：
#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m,dsu[500100],res=0x3f3f3f3f;
int find(int x){
return dsu[x]==x?x:dsu[x]=find(dsu[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return false;
dsu[x]=y;
return true;
}
struct edge{
int x,y,a,b;
friend bool operator <(const edge &u,const edge &v){
return u.a<v.a;
}
}e[100100];
struct LCT{
int ch[2],fa,val,mx;
bool rev;
}t[500100];
void pushup(int x){
t[x].mx=x;
if(t[t[x].mx].val<t[t[lson].mx].val)t[x].mx=t[lson].mx;
if(t[t[x].mx].val<t[t[rson].mx].val)t[x].mx=t[rson].mx;
}
void REV(int x){
t[x].rev^=1,swap(lson,rson);
}
void pushdown(int x){
if(!t[x].rev)return;
if(lson)REV(lson);
if(rson)REV(rson);
t[x].rev=false;
}
int identify(int x){
if(t[t[x].fa].ch[0]==x)return 0;
if(t[t[x].fa].ch[1]==x)return 1;
return -1;
}
void rotate(int x){
int y=t[x].fa;
int z=t[y].fa;
int dirx=identify(x);
int diry=identify(y);
int b=t[x].ch[!dirx];
if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
if(b)t[b].fa=y;t[y].ch[dirx]=b;
t[x].ch[!dirx]=y,t[y].fa=x;
pushup(y),pushup(x);
}
void pushall(int x){
if(identify(x)!=-1)pushall(t[x].fa);
pushdown(x);
}
void splay(int x){
pushall(x);
while(identify(x)!=-1){
int fa=t[x].fa;
if(identify(fa)==-1)rotate(x);
else if(identify(fa)==identify(x))rotate(fa),rotate(x);
else rotate(x),rotate(x);
}
}
void access(int x){
for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
access(x),splay(x),REV(x);
}
int findroot(int x){
access(x),splay(x);
pushdown(x);
while(lson)x=lson,pushdown(x);
splay(x);
return x;
}
int split(int x,int y){
makeroot(x),access(y),splay(y);
return t[y].mx;
}
void link(int x,int y){
makeroot(x),t[x].fa=y;
}
void cut(int x,int y){
split(x,y),t[x].fa=t[y].ch[0]=0,pushup(y);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
sort(e+1,e+m+1);
for(int i=1;i<=n+m;i++)t[i].val=0,t[i].mx=dsu[i]=i;
for(int i=n+1;i<=n+m;i++)t[i].val=e[i-n].b;
for(int i=1;i<=m;i++){
if(merge(e[i].x,e[i].y))link(e[i].x,n+i),link(n+i,e[i].y);
else{
int pos=split(e[i].x,e[i].y);
if(t[pos].val<e[i].b)continue;
cut(pos,e[pos-n].x),cut(pos,e[pos-n].y);
link(e[i].x,n+i),link(n+i,e[i].y);
}
if(find(1)==find(n))res=min(res,e[i].a+t[split(1,n)].val);
}
if(res==0x3f3f3f3f)puts("-1");
else printf("%d\n",res);
return 0;
}