BZOJ-2001. [HNOI2010]City城市建设

Posted by miskcoo on April 5, 2015

题目给定一个有 $n$ 个节点,$m$ 条边的有向图,以及 $q$ 个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,$n\leq 20000, m \leq 50000, q \leq 50000$

看了这篇题解才会做的

题目核心思想是分治以及缩小图的规模,有两个操作

Contraction:删除必须边

把待修改的边标记成 $-\infty$,然后跑一次最小生成树,显然这时候出现在生成树中非 $-\infty$ 的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边

Reduction:删除无用边

把待修改的边标记成 $\infty$,然后跑一次最小生成树,没出现在生成树中的非 $\infty$ 边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,$\infty$ 边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治

然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <cstdio>
#include <algorithm>

const int inf = ~0u >> 1;
const int MaxN = 20010, MaxM = 50010, MaxQ = MaxM, MaxL = 16;

struct edge_t
{
	int u, v, w, id;
	friend bool operator < (const edge_t& a, const edge_t& b)
	{
		return a.w < b.w;
	}
} edge[MaxL][MaxM], d[MaxM], t[MaxM];
struct ask_t
{
	int x, y;
} ques[MaxQ];
int fa[MaxM], size[MaxM], map[MaxM], weight[MaxM];
long long ans[MaxQ];

int find(int x)
{
	if(fa[x] == x)
		return x;
	return fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
	x = find(x), y = find(y);
	if(size[x] > size[y]) std::swap(x, y);
	size[y] += size[x], fa[x] = fa[y];
}

void reset(int n, const edge_t* e)
{
	for(int i = 0; i != n; ++i)
	{
		fa[e[i].u] = e[i].u;
		fa[e[i].v] = e[i].v;
		size[e[i].u] = size[e[i].v] = 1;
	}
}

long long contraction(int& n)
{
	int tmp = 0;

	std::sort(d, d + n);
	for(int i = 0; i != n; ++i)
	{
		if(find(d[i].u) != find(d[i].v))
		{
			merge(d[i].u, d[i].v);
			t[tmp++] = d[i];
		}
	}

	reset(tmp, t);
	long long v = 0;
	for(int i = 0; i != tmp; ++i)
	{
		if(t[i].w != -inf && find(t[i].u) != find(t[i].v))
		{
			merge(t[i].u, t[i].v);
			v += t[i].w;
		}
	}

	tmp = 0;
	for(int i = 0; i != n; ++i)
	{
		if(find(d[i].u) != find(d[i].v))
		{
			t[tmp] = d[i];
			t[tmp].u = fa[d[i].u];
			t[tmp].v = fa[d[i].v];
			map[d[i].id] = tmp++;
		}
	}

	reset(n, d); n = tmp;
	for(int i = 0; i != tmp; ++i)
		d[i] = t[i];
	return v;
}

void reduction(int& n)
{
	int tmp = 0;
	std::sort(d, d + n);
	for(int i = 0; i != n; ++i)
	{
		if(find(d[i].u) != find(d[i].v))
		{
			merge(d[i].u, d[i].v);
			t[tmp] = d[i];
			map[d[i].id] = tmp++;
		} else if(d[i].w == inf) {
			t[tmp] = d[i];
			map[d[i].id] = tmp++;
		}
	}

	reset(n, d); n = tmp;
	for(int i = 0; i != tmp; ++i)
		d[i] = t[i];
}

void divide(int now, int n, int l, int r, long long v)
{
	if(l == r) weight[ques[l].x] = ques[l].y;
	for(int i = 0; i != n; ++i)
	{
		edge[now][i].w = weight[edge[now][i].id];
		d[i] = edge[now][i];
		map[d[i].id] = i;
	}

	if(l == r)
	{
		ans[l] = v;
		std::sort(d, d + n);
		for(int i = 0; i != n; ++i)
		{
			if(find(d[i].u) != find(d[i].v))
			{
				merge(d[i].u, d[i].v);
				ans[l] += d[i].w;
			}
		}
		return reset(n, d);
	}

	for(int i = l; i <= r; ++i)
		d[map[ques[i].x]].w = -inf;
	v += contraction(n);

	for(int i = l; i <= r; ++i)
		d[map[ques[i].x]].w = inf;
	reduction(n);

	for(int i = 0; i != n; ++i)
		edge[now + 1][i] = d[i];

	int m = (l + r) >> 1;
	divide(now + 1, n, l, m, v);
	divide(now + 1, n, m + 1, r, v);
}

int main()
{
	int n, m, q;
	std::scanf("%d %d %d", &n, &m, &q);

	for(int i = 0; i <= n; ++i)
		fa[i] = i, size[i] = 1;

	for(int i = 0; i != m; ++i)
	{
		int u, v, w;
		std::scanf("%d %d %d", &u, &v, &w);
		edge[0][i].u = u, edge[0][i].v = v;
		edge[0][i].w = w, edge[0][i].id = i;
		weight[i] = w;
	}

	for(int i = 0; i != q; ++i)
	{
		std::scanf("%d %d", &ques[i].x, &ques[i].y);
		--ques[i].x;
	}

	divide(0, m, 0, q - 1, 0);
	for(int i = 0; i != q; ++i)
		std::printf("%lld\n", ans[i]);
	return 0;
}