这个题就是先按照 a 从小到大排序, 然后 lct 尽可能维护 b 值最小, 在这个过程中寻找答案
- #include<algorithm>
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<cmath>
- using namespace std;
- int x,y,a,b;
- struct in
- {
- int f,l,a,b;
- }ter[100010];
- int son[200020][2],pre[200020],s1[200020],s[200020],fa[200020],lin[200020],n,m,ans = 1000000007;//lct 并不是一棵实际存在的树(类似树链剖分, 只不过现在是一棵 splay), 所以我们单独建树
- //son 存储 splay 的蛾子, pre 存储 splay 的父亲(因为被分成一块块的树, 就如树剖)
- bool flag[200020];
- inline void re(int &x)
- {
- x = 0;
- bool fl = 0;
- char a = getchar();
- while(a < 0 || a > 9)
- {
- if(a == -)
- fl = 1;
- a = getchar();
- }
- while(a >= 0 && a <= 9)
- x = x * 10 + a - 0,a = getchar();
- }
- bool cmp(in a,in b)
- {
- return a.a < b.a;
- }
- int find(int x)// 并查集日常操作
- {
- return fa[x] == x ? x : fa[x] = find(fa[x]);
- }
- bool isroot(int x)// 判断是不是根
- {
- return son[pre[x]][0] != x && son[pre[x]][1] != x;
- }
- void spread(int x)// 翻转
- {
- if(!flag[x])
- return;
- swap(son[x][0],son[x][1]);// 左右蛾子互换
- flag[son[x][0]] ^= 1,flag[son[x][1]] ^= 1,flag[x] = 0;
- }
- void up(int x)// 更新
- {
- int ls = son[x][0],rs = son[x][1];
- s1[x] = x;
- if(s[s1[ls]] > s[s1[x]]) s1[x] = s1[ls];
- if(s[s1[rs]] > s[s1[x]]) s1[x] = s1[rs];
- }
- bool dir(int x)// 判断蛾子与父亲的相对关系
- {
- return son[pre[x]][1] == x;
- }
- void rotate(int x)// 日常旋转
- {
- int d = dir(x),f = pre[x],g = pre[f];
- if(!isroot(f))
- son[g][dir(f)] = x;
- son[f][d] = son[x][d ^ 1],pre[son[x][d ^ 1]] = f,son[x][d ^ 1] = f;
- up(g),up(f),pre[x] = g,pre[f] = x;
- }
- void splay(int x)
- {
- int i;
- for(i = x;!isroot(i);i = pre[i])// 作为栈记录一下需要清空标记的点
- lin[++ lin[0]] = i;
- lin[++ lin[0]] = i;
- while(lin[0])// 清空标记
- spread(lin[lin[0] --]);
- while(!isroot(x))// 正常旋转
- {
- int y = pre[x],z = pre[y];
- if(!isroot(y))
- {
- if((son[pre[y]][1] == y) == (son[pre[z]][1] == z))
- rotate(y);
- else
- rotate(x);
- }
- rotate(x);
- }
- up(x);
- }
- void access(int x)// 打通 x 到树根的路径
- {
- int la = 0;
- while(x)// 直到树根
- {
- splay(x);// 把 x 转到子树的树根
- son[x][1] = la,la = x,x = pre[x];// 然后把 x 的父亲 (在上层子树上) 进行旋转
- }
- }
- void makeroot(int x)// 先让 x 和树根在同一个 splay, 然后再旋转到树根, 打上标记(因为换根操作中只有蛾子与父亲的相对关系发生改变)
- {
- access(x),splay(x),flag[x] ^= 1;
- }
- void ask(int x,int y)// 询问树上信息的时候, 先把 x 转到树根, 再使得 y 连接到树根
- {
- makeroot(x),access(y),splay(y);
- }
- void link(int x,int y)// 先把 x 旋转到树根, 然后把 y 作为 x 的父亲, 这样就链接了
- {
- makeroot(x),pre[x] = y;
- }
- void cut(int x,int y)// 切断的时候要先把 x 作为 y 的左蛾子(因为 ask 函数使得这两者相连), 然后再清除一下 pre,son 数组
- {
- ask(x,y),pre[x] = son[y][0] = 0;
- }
- int main()
- {
- re(n),re(m);
- for(int i = 1;i <= m;i ++)
- re(ter[i].f),re(ter[i].l),re(ter[i].a),re(ter[i].b);
- sort(ter + 1,ter + 1 + m,cmp);// 先保证 a 种精灵是按照最小生成树维护
- for(int i = 1;i <= n;i ++)
- fa[i] = i;
- for(int i = 1;i <= m;i ++)
- {
- s[i + n] = ter[i].b;
- int fx = find(ter[i].f),fy = find(ter[i].l);
- if(fx != fy)// 如果这两个点不相连, 直接将两者合并到一个集合
- link(i + n,ter[i].f),link(i + n,ter[i].l),fa[fx] = fy;
- else
- {
- ask(ter[i].f,ter[i].l);// 否则加进去说明出现了环, 那么找环上 b 最大的边替换掉
- int no = s1[ter[i].l];// 我们用虚点来作为两个点的中转站
- if(s[i + n] >= s[no])// 如果现在要加的边的 b 值比环上 b 最大的边还要大的, 就没有必要替换了
- continue;
- cut(no,ter[no - n].f),cut(no,ter[no - n].l);// 我们把原来那条边拆掉
- link(i + n,ter[i].f),link(i + n,ter[i].l);// 再用新的边替换
- }
- int ff = find(1),fg = find(n);
- if(ff == fg)// 如果发现现在起点到终点可以联通, 试图更新答案(因为 a 变大了)
- ask(1,n),ans = min(ans,ter[i].a + s[s1[n]]);
- }
- if(ans >= 1000000007)
- printf("-1");
- else
- printf("%d",ans);
- }
来源: http://www.bubuko.com/infodetail-2499059.html