题目链接
\(Solution\)
两个变量,emm...不好搞啊。
于是我们可以按照\(A\)排序。然后动态加边,因为\(A\)是越来越大,所以不需要管他,只要使得\(1\)~\(n\)的路径中\(B\)最大值最小。这用LCT维护生成树就好了,模板题。每次加边后满足\(1\)~\(n\)有路径的时候将
此时最大的\(B\)+当前\(A\),去\(min\),最后输出即可\(Code\)
#include#define rg register#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);using namespace std;int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return f*x;}struct node { int v,lazy,ch[2],fa;}a[2000001];int v[2000001],pre[2000001];int max(int x,int y){ return v[x]>v[y]?x:y;}void pushup(int x){ a[x].v=max(x,max(a[a[x].ch[0]].v,a[a[x].ch[1]].v));}bool nroot(int x){ return a[a[x].fa].ch[0]==x||a[a[x].fa].ch[1]==x;}void work(int x){ swap(a[x].ch[1],a[x].ch[0]),a[x].lazy^=1;}void pushdown(int x){ if(a[x].lazy){ if(a[x].ch[0]) work(a[x].ch[0]); if(a[x].ch[1]) work(a[x].ch[1]); a[x].lazy=0; }}void pushall(int x){ if(nroot(x)) pushall(a[x].fa); pushdown(x);}void rotate(int x){ int y=a[x].fa,z=a[y].fa,k=a[y].ch[1]==x; if(nroot(y)) a[z].ch[a[z].ch[1]==y]=x; a[x].fa=z,a[y].ch[k]=a[x].ch[k^1],a[a[x].ch[k^1]].fa=y; a[x].ch[k^1]=y,a[y].fa=x,pushup(y),pushup(x);}void splay(int x){ pushall(x); while(nroot(x)){ int y=a[x].fa,z=a[y].fa; if(nroot(y)) (a[y].ch[1]==x)^(a[z].ch[1]==y)?rotate(x):rotate(y); rotate(x); } pushup(x);}void access(int x){ for(int y=0;x;y=x,x=a[x].fa) splay(x),a[x].ch[1]=y,pushup(x);}void makeroot(int x){ access(x),splay(x),work(x);}int findroot(int x){ access(x),splay(x); while(a[x].ch[0]) pushdown(x),x=a[x].ch[0]; splay(x); return x;}void splix(int x,int y){ makeroot(x),access(y),splay(y);}void link(int x,int y){ makeroot(x); if(findroot(y)!=x) a[x].fa=y;}void cut(int x,int y){ makeroot(x); if(findroot(y)!=x||a[y].fa!=x||a[y].ch[0]) return; a[x].ch[1]=a[y].fa=0,pushup(x);}struct node1 { int x,y,z,v;}b[1000010];bool cmp(const node1 & a , const node1 & b ){ return a.z b[i].v) cut(b[x-n].x,x),cut(b[x-n].y,x),link(b[i].x,i+n),link(b[i].y,i+n); } if(find(1)==find(n)) splix(1,n),minx=min(minx,v[a[n].v]+b[i].z); } if(minx==2147483647) puts("-1"),exit(0); printf("%d",minx); return 0;}