BZOJ-2001. [HNOI2010]City城市建设
题目给定一个有 $n$ 个节点,$m$ 条边的有向图,以及 $q$ 个修改,每个修改更改一条边的权值,并且询问修改后的图的最小生成树,$n\leq 20000, m \leq 50000, q \leq 50000$
看了这篇题解才会做的
题目核心思想是分治以及缩小图的规模,有两个操作
Contraction:删除必须边
把待修改的边标记成 $-\infty$,然后跑一次最小生成树,显然这时候出现在生成树中非 $-\infty$ 的边肯定会在之后的生成树中,所以我们记录下它们的权值和,然后在下一层分治的时候删除这些边
Reduction:删除无用边
把待修改的边标记成 $\infty$,然后跑一次最小生成树,没出现在生成树中的非 $\infty$ 边在之后的生成树中肯定也不会出现(因为在当前图构造出的MST中,加入这条边会生成一个环,而且它是这个环中权值最大的边,然而在之后的图中,$\infty$ 边只会变小,它还是权值最大的边,所以肯定不会出现在MST中),于是将它们删除,继续分治
然后每层分治过程中都进行 Contraction-Reduction 来缩小图的规模,在最后一层分治的时候使修改生效,做一遍MST就可以了(这时候图已经很小了所以会很快)
#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;
}