洛谷

BZOJ

题目描述

给你一张边带权的无向连通图,多次修改,每次修改一条边的边权,每次修改完后求最小生成树的边权之和。

点数 $2\cdot 10^4$, 边数和修改数 $5\cdot 10^4$,时限 3s。

简要做法

LCT 做法

把每条边按两次修改之间以及头尾分成若干段,然后按出现时间线段树分治,LCT 维护最小生成树。

时间复杂度 $O(n+(m+q)\log q\log n)$ ,常数有点大,听说很难卡到满分,自己没写。

Kruskal 做法

还是线段树分治,但尝试用 Kruskal 算法求最小生成树。

然而,Kruskal 算法要求边权从小到大加入,直接线段树分治无法满足这个要求。

(注:为了严谨,你可以认为下文中在比较大小时给第 $i$ ($1\le i\le m$) 条边的边权加上了 $2^{-i}$,这样保证了 MST 是唯一的。当然,在代码中无需如此。)

可以观察到,随着分治区间越来越小,修改的边也越来越少,图中大多数的边是不会被修改的。正因如此,可以猜想,大多数边在或不在 MST 中是固定的,而我们需要关注的,只有那些因会修改的边的边权变化而既可能在 MST 中又可能不在 MST 中的边。

如果我们有一张图 $G=(V, E)$,其中 $E’\subseteq E$ 是以后会被修改的边,那么,如何求出那些无论 $E'$ 中的边边权如何变化都一定在 MST 中/一定不在 MST 中的边呢?

  1. 将 $E'$ 中的边边权设为正无穷,求 MST,此时不在 $E'$ 中且不在 MST 中的边,无论 $E'$ 中的边边权如何变化,都不在 MST 中,下文中称这些边为“一类边”。
  2. 将 $E'$ 中的边边权设为 $0$,求 MST,此时不在 $E'$ 中且在 MST 中的边,无论 $E'$ 中的边边权如何变化,都在 MST 中,下文中称这些边为“二类边”。

那么,在继续分治下去的过程中,我们就只需关注 $E'$ 中的边以及是一类边而不是二类边的边。

由于一类边最多有 $|V|-1$ 条,而二类边至少有 $|V|-1-|E'|$ 条,所以是一类边而不是二类边的边最多有 $|E'|$ 条,于是,向下分治时需要关注的边就不超过 $2|E'|$ 条。

虽然只需关注这些边,但二类边依然要在分治过程中保留(计算 MST 时并查集中要保留,最后边权要计入答案)。边权计入答案很好办,而保留在并查集中可以通过可回退并查集来实现。

一层分治中每个分治内会被修改的边加起来是 $O(m+q)$ 条,并查集要可回退,只能按秩合并。所以总时间复杂度是 $O(n+(m+q)\log(m+q)+(m+q)\log q\log n)$ 。

时间复杂度和 LCT 做法差不多(你愿意的话你可以说时间复杂度更大),但跑得飞快。

有个实现上的小细节:将 $E'$ 中的边边权设为无穷大和 $0$ 时不需要真的修改再排序,最后加入(其实可以直接不加入)/最先加入即可,而其它边的排序可以在主函数中完成,而在分治过程中保持原序。这样时间复杂度的瓶颈上就只有并查集而没有排序了(当然我说的是 (m+q)logqlogn 这个瓶颈,不是 (m+q)log(m+q) 这个瓶颈)。

Kruskal 做法参考代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Edge
{
	int u, v, w, l, r;
	bool operator<(const Edge &b) const
	{
		return w < b.w;
	}
	
	bool change(int left, int right)
	{
		return (l > left && l <= right) || (r >= left && r < right);
	}
};

struct UFS
{
	vector<int> f, siz;
	
	struct Change
	{
		int x, y;
	};
	
	stack<Change> c;
	
	void init(int n)
	{
		f.resize(n + 1);
		siz.resize(n + 1, 1);
		for (int i = 0; i <= n; ++i) f[i] = i;
	}
	
	int find(int x)
	{
		return x == f[x] ? x : find(f[x]);
	}
	
	bool merge(int x, int y)
	{
		x = find(x);
		y = find(y);
		if (x == y) return false;
		if (siz[x] < siz[y]) swap(x, y);
		c.push({x, y});
		siz[x] += siz[y];
		f[y] = x;
		return true;
	}
	
	void rollback(int x)
	{
		while ((int)c.size() > x)
		{
			f[c.top().y] = c.top().y;
			siz[c.top().x] -= siz[c.top().y];
			c.pop();
		}
	}
	
	int status() const { return c.size(); }
} ufs;

vector<ll> ans;

void solve(int l, int r, vector<Edge> &e, ll delta = 0)
{
	if (l == r)
	{
		ans[l] = delta;
		int ver = ufs.status();
		for (int i = 0; i < (int)e.size(); ++i) if (ufs.merge(e[i].u, e[i].v)) ans[l] += e[i].w;
		ufs.rollback(ver);
		return;
	}
	vector<bool> ininf(e.size(), false), inzero(e.size(), false);
	int ver = ufs.status();
	for (int i = 0; i < (int)e.size(); ++i) if (!e[i].change(l, r)) ininf[i] = ufs.merge(e[i].u, e[i].v);
	ufs.rollback(ver);
	for (int i = 0; i < (int)e.size(); ++i) if (e[i].change(l, r)) ufs.merge(e[i].u, e[i].v);
	for (int i = 0; i < (int)e.size(); ++i)
	{
		if (!e[i].change(l, r) && ufs.merge(e[i].u, e[i].v))
		{
			inzero[i] = true;
			delta += e[i].w;
		}
	}
	int mid = (l + r) >> 1;
	vector<Edge> le, re;
	for (int i = 0; i < (int)e.size(); ++i)
	{
		if (e[i].change(l, r) || (ininf[i] && !inzero[i]))
		{
			if (e[i].l <= mid) le.push_back(e[i]);
			if (e[i].r > mid) re.push_back(e[i]);
		}
	}
	ufs.rollback(ver);
	for (int i = 0; i < (int)e.size(); ++i) if (inzero[i]) ufs.merge(e[i].u, e[i].v);
	solve(l, mid, le, delta);
	solve(mid + 1, r, re, delta);
	ufs.rollback(ver);
}

int main()
{
	int n, m, q;
	
	scanf("%d%d%d", &n, &m, &q);
	
	vector<Edge> e;
	vector<int> u(m), v(m), w(m), last(m, 1);
	
	for (int i = 0; i < m; ++i) scanf("%d%d%d", &u[i], &v[i], &w[i]);
	
	for (int i = 1; i <= q; ++i)
	{
		int p, x;
		scanf("%d%d", &p, &x);
		--p;
		if (i > 1) e.push_back({u[p], v[p], w[p], last[p], i - 1});
		last[p] = i;
		w[p] = x;
	}
	
	for (int i = 0; i < m; ++i) e.push_back({u[i], v[i], w[i], last[i], q});
	
	sort(e.begin(), e.end());
	
	ans.resize(q + 1);
	ufs.init(n);
	
	solve(1, q, e);
	
	for (int i = 1; i <= q; ++i) printf("%lld\n", ans[i]);
	
	return 0;
}