Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P2387 [NOI2014] 魔法森林

Posted on

题目传送门

solution：

  • 优先按照 $A$ 为关键字排序，然后按照顺序，动态加边，使边的代价变成 $B$ 的最大值，则加入第 $i$ 条边后的最小代价就是 $A_i$ + $\min_1^n{v_i}$。
  • 动态加边， $LCT$ 的裸题，但是题目中的代价明显是在边上，怎么办呢，我们可以将边拆成（边-点-边），将边上的代价等价转移到点上。断开时在相应的选择代价最大的边就可以了

代码：

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
const int N = 150010, Inf = 1e9 + 5;
int n, m;
struct Edge{
	int x, y, a, b;
	bool operator< (const Edge& t) const
	{
		return a < t.a;
	}
}e[N];
struct Node{
	int s[2], p, v;
	int mx, rev;
}tr[N];
int stk[N], p[N];
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x]; 
} 
void pushrev(int x)
{
	swap(tr[x].s[0], tr[x].s[1]);
	tr[x].rev ^= 1;
}
void pushup(int x)
{
	tr[x].mx = x;
	for(int i = 0;i < 2;i ++)
	{
		if(tr[tr[tr[x].s[i]].mx].v > tr[tr[x].mx].v)
			tr[x].mx = tr[tr[x].s[i]].mx;
	}
} 
void pushdown(int x)
{
	if(tr[x].rev)
	{
		pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
		tr[x].rev = 0;
	}
}
bool isroot(int x)
{
	return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}
void rotate(int x)
{
	int y = tr[x].p, z = tr[y].p;
	int k = tr[y].s[1] == x;
	if(!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
	tr[x].p = z;
	tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
	tr[x].s[k ^ 1] = y, tr[y].p = x;
	pushup(y), pushup(x);
}  
void splay(int x)
{
	int top = 0, r = x;
	stk[++ top] = r;
	while(!isroot(r)) stk[++ top] = r = tr[r].p;
	while(top) pushdown(stk[top --]);
	while(!isroot(x))
	{
		int y = tr[x].p, z = tr[y].p;
		if(!isroot(y))
		{
			if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)// 建立一条从根到x的路径，同时将x变成splay的根节点
{
	int z = x;
	for(int y = 0; x; y = x, x = tr[x].p)
	{
		splay(x);
		tr[x].s[1] = y, pushup(x);
	}
	splay(z);
}
void make_root(int x)// 将x变为原树的根节点 
{
	access(x);
	pushrev(x);
}
int find_root(int x)//找到x所在的原树根节点，再将原树的根节点旋转到splay的根节点 
{
	access(x);
	while(tr[x].s[0]) pushdown(x), x = tr[x].s[0];
	splay(x);
	return x; 
}
void split(int x,int y)// 给x和y之间的路径建立一个splay，其根节点是y
{
	make_root(x);
	access(y);
}
void link(int x, int y)// 如果x和y不连通，则加入一条x和y之间的边
{
	make_root(x);
	if(find_root(y) != x) tr[x].p = y;
}
void cut(int x, int y)// 如果x和y之间存在边，则删除该边
{
	make_root(x);
	if(find_root(y) == x && tr[y].p == x && !tr[y].s[0])
	{
		tr[x].s[1] = tr[y].p = 0;
		pushup(x);
	} 
}
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 ++)
	{
		p[i] = i;
		if(i > n) tr[i].v = e[i - n].b;
		tr[i].mx = i;
	} 
	int res = Inf;
	for(int i = 1;i <= m;i ++)
	{
		int x = e[i].x, y = e[i].y, a = e[i].a, b = e[i].b;
		if(find(x) == find(y))
		{
			split(x, y);
			int t = tr[y].mx;
			if(tr[t].v > b)
			{
				cut(e[t - n].x, t), cut(t, e[t - n].y);
				link(x, n + i), link(n + i, y); 
			} 
		}
		else
		{
			p[find(x)] = find(y);
			link(x, n + i), link(n + i, y); 
		}
		if(find(1) == find(n))
		{
			split(1, n);
			res = min(res, a + tr[tr[n].mx].v);
		}
	}
	if(res == Inf) res = -1;
	printf("%d\n", res);
	return 0;
}