「NOI2014」魔法森林

本文主要是介绍「NOI2014」魔法森林 - 动态树LCT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个 $N$ 节点 $M$ 条边的无向图，节点标号为 $1\cdots N$ ，边标号为 $1\cdots M$ 。初始时小E同学在号节点 $1$ ，隐士则住在号节点 $N$ 。小E需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵： $A$ 型守护精灵与 $B$ 型守护精灵。小E可以借助它们的力量，达到自己的目的。

只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 $E_i$ 包含两个权值 $A_i$ 与 $B_i$ 。若身上携带的 $A$ 型守护精灵个数不少于 $A_i$ ，且 $B$ 型守护精灵个数不少于 $B_i$ ，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 $A$ 型守护精灵的个数与 $B$ 型守护精灵的个数之和。

输入格式

第1行包含两个整数 $N, M$ ，表示无向图共有 $N$ 个节点， $M$ 条边。接下来 $M$ 行，第行包含 $4$ 个正整数 $Xi_,Y_i,A_i,B_i$ ，描述第 $i$ 条无向边。其中 $X_i$ 与 $Y_i$ 为该边两个端点的标号， $A_i$ 与 $B_i$ 的含义如题所述。注意数据中可能包含重边与自环。

输出格式

输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出-1。

分析

如果没有 $B$ 型守护精灵，那么就是求 $1$ ~ $N$ 的所有路径中最大边权的最小值。很容易想到用最小生成树解决。现在一条边有两个权值，同样按照Kruskal算法的思路，固定边的一种权值 $A_i$ ，将其按从小到大排序，然后就可以发现，答案中 $B_i$ 就一定在以 $B_i$ 为权值的最小生成树上，于是就可以用LCT维护 $B$ 的最小生成树。当 $1$ 和 $N$ 连通时就更新答案。对于自环与重边，可以不处理，LCT会自动过滤。似乎还有一种用Spfa的方法，供大家思考。 ~~（LCT也没那么长，压行后百行都不到）~~

代码

#include <algorithm>
#include <climits>
#include <cstdio>
using namespace std;
const int N=500005,M=100005;
const int V=N+M,INF=INT_MAX>>1;
typedef long long LL;
struct Edge {int u,v,ca,cb;}e[M];
int n,m,fa[N],ans;
bool cmp(Edge a,Edge b) {return a.ca<b.ca;}
int getf(int x) {return fa[x]==x?x:fa[x]=getf(fa[x]);}
int c[V][2],f[V];
int mx[V],v[V],rv[V],st[V];
void init(int x,int p) {mx[x]=v[x]=p;}
bool nroot(int x) {return c[f[x]][0]==x||c[f[x]][1]==x;}
void makerv(int x) {rv[x]^=1;swap(c[x][0],c[x][1]);}
void pushup(int x) {mx[x]=v[x];if (e[mx[c[x][0]]].cb>e[mx[x]].cb) mx[x]=mx[c[x][0]];if (e[mx[c[x][1]]].cb>e[mx[x]].cb) mx[x]=mx[c[x][1]];
}
void pushdown(int x) {if (!x||!rv[x]) return;if (c[x][0]) makerv(c[x][0]);if (c[x][1]) makerv(c[x][1]);rv[x]=0;
}
void pushtg(int x) {int top=0;st[++top]=x;while (f[x]) st[++top]=(x=f[x]);while (top) pushdown(st[top--]);
}
void rotate(int x) {int y=f[x],z=f[y];int k=c[y][1]==x;if (nroot(y)) c[z][c[z][1]==y]=x;f[x]=z;f[y]=x;if (c[x][k^1]) f[c[x][k^1]]=y;c[y][k]=c[x][k^1];c[x][k^1]=y;pushup(y);pushup(x);
}
void splay(int x) {pushtg(x);for (int y,z;y=f[x],z=f[y],nroot(x);rotate(x))if (nroot(y)) rotate((c[y][0]==x)^(c[z][0]==y)?x:y);pushup(x);
}
void access(int x) {for (int y=0;x;splay(x),c[x][1]=y,pushup(x),x=f[y=x]);}
void makert(int x) {access(x);splay(x);makerv(x);}
void split(int x,int y) {makert(x);access(y);splay(y);}
void link(int x,int y) {makert(x);f[x]=y;pushup(y);}
void cut(int x,int y) {split(x,y);f[x]=c[y][0]=0;pushup(y);}
int main() {scanf("%d%d",&n,&m);for (int i=1;i<=m;i++) {int u,v,a,b;scanf("%d%d%d%d",&u,&v,&a,&b);e[i]=(Edge){u,v,a,b};}sort(e+1,e+m+1,cmp);for (int i=1;i<=n;i++) init(i,0),fa[i]=i;for (int i=n+1;i<=n+m;i++) init(i,i-n);ans=INF;for (int i=1;i<=m;i++) {int u=e[i].u,v=e[i].v;int fu=getf(u),fv=getf(v);if (fu!=fv) link(u,i+n),link(i+n,v),fa[fu]=fv;else {split(u,v);int num=mx[v];if (e[num].cb>e[i].cb) {cut(e[num].u,num+n);cut(num+n,e[num].v);link(u,i+n);link(i+n,v);}}if (getf(1)==getf(n)) {split(1,n);ans=min(ans,e[i].ca+e[mx[n]].cb);}}if (ans==INF) printf("-1");else printf("%d",ans);return 0;
}