关键词:Link-Cut Tree   动态树 相关题目:[NOI2014]魔法森林 题意:给定一张无向图,每条边有两种元素a, b。你需要求出从起点到终点的每一条路径中a的最大值与 b的最大值之和的最小值。

Description

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

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

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

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

Input

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

Output

输出一行一个整数:如果小E可以成功拜访到隐士,输出小E最少需要携带的守护精灵的总个数;如果无论如何小E都无法拜访到隐士,输出“-1”(不含引号)。

Sample Input 【输入样例1】

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

【输入样例2】

3 1
1 2 1 1

Sample Output 【输出样例1】

32

【样例说明1】

如果小E走路径1→2→4,需要携带19+15=34个守护精灵;

如果小E走路径1→3→4,需要携带17+17=34个守护精灵;

如果小E走路径1→2→3→4,需要携带19+17=36个守护精灵;

如果小E走路径1→3→2→4,需要携带17+15=32个守护精灵。

综上所述,小E最少需要携带32个守护精灵。

【输出样例2】

-1

【样例说明2】

小E无法从1号节点到达3号节点,故输出-1。

HINT

2<=n<=50,000      0<=m<=100,000      1<=ai ,bi<=50,000

Solution

常规套路:枚举一个元素,最优化另一个元素

我们考虑枚举元素 a,最优化元素 b。显然,若加入的边为ee,那么答案必然 min(e.a+min(b))\text{min(e.a+min(b))} 取到。

所以可以通过 Link-Cut Tree 动态连、删边维护关于b的最小生成树,那么 min(b)\text{min(b)} 就是 1n1-n 路径上的 bb 的最大值。

那么怎么构造Link-Cut Tree呢?我们不妨把边看成点,而原图里的点权值为0.

如果加入边 ee 的话发现其两个顶点已经连通,那么就需要进行删边操作。这时必须贪心把 bb 最大的边删除。(所以update的时候维护一下该Splay中 bb 最大的点就好了)

SPFA加边跑最短路

emm...同样枚举 a,动态加边跑SPFA得到 bb 的最大值。但是复杂度... 听说是 O(能过)

AC代码

Link-Cut Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <cctype>
#include <algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 100020, M = 400020, inf=0x7f7f7f7f;
inline int read() {
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}

int index, val[M], s[M][2], fa[M], rev[M], Max[M];
#define lson(x) s[x][0]
#define rson(x) s[x][1]
int n, m;
class Edge {
public: int u, v, a, b;
inline bool operator < (const Edge& rhs)const {
return a < rhs.a;
}
} e[N];

inline void update(int x) {
Max[x] = x;
if(val[Max[lson(x)]]>val[Max[x]]) Max[x]=Max[lson(x)];
if(val[Max[rson(x)]]>val[Max[x]]) Max[x]=Max[rson(x)];
}
inline void pushdown(int x) {
if(rev[x])
{ rev[lson(x)]^=1,rev[rson(x)]^=1,rev[x]=0;
std::swap(lson(x), rson(x)); }
}
inline bool isroot(int x) { return lson(fa[x])!=x&&rson(fa[x])!=x;}
void rotate(int x) {
int f=fa[x], p=fa[f], d=(s[f][1]==x);
if(!isroot(f)) s[p][s[p][1]==f]=x; //connect(p, x)
s[f][d]=s[x][d^1], fa[s[x][d^1]]=f; //connect(f, s[x][d^1])
s[x][d^1]=f, fa[f]=x; fa[x]=p; //connect(x, f)
update(f), update(x);
}
int q[M], siz;
void splay(int x) {
q[siz=1]=x; for(re i=x;!isroot(i);i=fa[i]) q[++siz]=fa[i];
while(siz) pushdown(q[siz--]);
for(re f=fa[x],p=fa[f]; !isroot(x); f=fa[x],p=fa[f]) {
if(!isroot(f))
rotate((lson(f)==x)^(lson(p)==f)?x:f);
rotate(x);
}
}

void access(int x) { for(re t=0;x;t=x,x=fa[x]) splay(x),rson(x)=t,update(x);}
void makeroot(int x) { access(x),splay(x); rev[x]^=1;}
int findroot(int x) { access(x),splay(x); while(lson(x)) x=lson(x); return x;}
void split(int x, int y) { makeroot(x),access(y),splay(y);}
void link(int x, int y) { makeroot(x); fa[x]=y;}
void cut(int x, int y) { split(x, y); fa[x]=lson(y)=0; update(y);}
int query(int x, int y) { split(x, y); return Max[y];}
void add(int x, int y, int w) {
val[++index] = w;
if(findroot(x)==findroot(y)) {
int p = query(x, y);
if(w < e[p-n].b) {
cut(e[p-n].u, p), cut(e[p-n].v, p);
link(x, index), link(y, index);
}
}
else link(x, index), link(y, index);
}

int main() {
n=read(), m=read();
rep(i,1,m) e[i] = (Edge){read(),read(),read(),read()};
std::sort(e+1, e+m+1);

int ans=inf; index=n;
rep(i,1,m) {
add(e[i].u, e[i].v, e[i].b);
if(findroot(1)==findroot(n))
ans = min(ans, e[i].a+val[query(1,n)]);
}
printf("%d\n", ans==inf?-1:ans);
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define pii pair<int, int>
const int N = 50020, M = 100020, inf=0x7f7f7f7f;
inline int read() {
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}

class Edge {
public: int u,v,a,b;
inline bool operator < (const Edge& rhs)const{
return a < rhs.a;
}
} e[M];
int cnt=0, nxt[M*2], head[N], to[M*2], b[M*2];
inline void add(int u, int v, int w2)
{nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,b[cnt]=w2;}
#define travel(i,u) for(re i=head[u];i;i=nxt[i])

int n, m, f[N], vis[N];
queue<int> q;

inline void spfa(int s, int t) {
q.push(s), q.push(t);
vis[s] = vis[t] = 1;
int u, v, r;
while(!q.empty()) {
u=q.front(), q.pop(), vis[u]=0;
travel(i,u) {
v = to[i];
if((r=max(f[u], b[i])) < f[v]) {
f[v] = r;
if(!vis[v]) q.push(v), vis[v]=1;
}
}
}
}

int main() {
n=read(), m=read();
rep(i,1,m) e[i] = (Edge){read(),read(),read(),read()};
sort(e+1, e+m+1);

int ans=inf;
memset(f, 0x7f, sizeof f), f[1]=0; q.push(1), vis[1]=1;
rep(i,1,m) {
add(e[i].u, e[i].v, e[i].b);
add(e[i].v, e[i].u, e[i].b);
spfa(e[i].u, e[i].v);
ans = min(ans, e[i].a+f[n]);
}
printf("%d\n", ans==inf?-1:ans);
}