@atcoder - CODE FESTIVAL 2017 Final

@description@
@solution@
@accepted code@
@details@

@description@

给定 N 个点，第 i 点有一个点权 Xi，再给定一棵边带权的树，第 i 条 (Ai, Bi) 边权为 Ci。

构建一个完全图，完全图中边 (i, j) 的边权为 dist(i, j) + Xi + Xj，其中 dist(i, j) 是点 i 与点 j 在树上的距离。

求该完全图的最小生成树。

Constraints

2≤N≤200000; 1≤Xi≤10^9; 1≤Ai,Bi≤N; 1≤Ci≤10^9

Input

输入形式如下：

N

X1 X2 … XN

A1 B1 C1

A2 B2 C2

:

AN−1 BN−1 CN−1

Output

输出最小生成树的边权总和。

Sample Input 1

4

1 3 5 1

1 2 1

2 3 2

3 4 3

Sample Output 1

22

选择边 (1, 2), (1, 4), (3, 4)，边权总和为 5 + 8 + 9 = 22

点此跳转到题目

@solution@

完全图并不能直接套 prim 或者 kruskal。

并且也不像最小曼哈顿生成树一样，有比较好用的性质可以去除大量无用边。

考虑这类题的一个通用解法：boruvka（不会念）。

其实是基本无人问津的最小生成树算法（我也不知道为什么），但是可以将其算法思想拓展，解决一些完全图的最小生成树问题。

说是完全图，边权也有性质，而且往往会和点权挂钩（比如这道题）。

扯了这么多，所谓的 boruvka 算法是什么呢？

我们对于每一个连通块去找与它相邻的最小边。可以证明这样的边一定是存在于最小生成树之中（破圈法之类的都能证）。

于是我们把这些边加入最小生成树，并将连通块合并。

因为每次选最小边的时候，一条边最多会被选两次，所以最多执行 log 次寻找最小边的操作。

而这类题的特点是：往往寻找最小边的过程可以优化。

什么？你说这道题需要点分治来寻找路径最小值？然后复杂度就炸成 O(nlog^3n) 了？

NONONO。我们其实可以 O(n) 一次性给所有点找到它对应的最小值。

考虑所有连通块都是一个点的时候，我们可以做一个换根 dp 求出所有点的最小边（求距离一个点最近的点）。

由于是找最小值，重复经过一条边肯定不优，我们甚至不用去存 dp 的次小值，来避免从上往下传递 dp 值的时候走入同一棵子树。

这个过程是 O(n) 的。

那么连通块是一堆点的时候，我们怎么去排除与它同一连通块的点呢？

其实。。。很简单嘛。

假如最小边是同一连通块的，我们就去找与最小边不在同一连通块的次小边，不就解决了嘛。

dp 的时候存两维：最小边，与不和最小边在同一连通块的次小边。转移时讨论一下即可。

一次求最小边的复杂度为 O(n)，所以总复杂度为 O(nlogn)。

@accepted code@

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

#define mp make_pair

#define fi first

#define se second

typedef pair<ll, int> pli;

typedef pair<pli, pli> st;

const int MAXN = 200000;

const ll INF = (1LL<<60);

struct edge{

	int to; ll dis;

	edge *nxt;

}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = edges;

void addedge(int u, int v, int w) {

	edge *p = (++ecnt);

	p->to = v, p->dis = w, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->dis = w, p->nxt = adj[v], adj[v] = p;

}

pli lnk[MAXN + 5];

int fa[MAXN + 5], clr[MAXN + 5];

ll X[MAXN + 5];

int find(int x) {

	return fa[x] = (fa[x] == x ? x : find(fa[x]));

}

bool unite(int x, int y) {

	int fx = find(x), fy = find(y);

	if( fx != fy ) {

		fa[fx] = fy;

		return true;

	}

	else return false;

}

st dp[MAXN + 5];

void update(st &a, st b) {

	if( b.fi.fi < a.fi.fi ) {

		if( b.fi.se != a.fi.se )

			a.se = a.fi;

		a.fi = b.fi;

		if( b.se.fi < a.se.fi )

			a.se = b.se;

	}

	else {

		if( b.fi.se != a.fi.se ) {

			if( b.fi.fi < a.se.fi )

				a.se = b.fi;

		}

		else if( b.se.fi < a.se.fi )

			a.se = b.se;

	}

}

void dfs1(int x, int f) {

	dp[x] = mp(mp(X[x], clr[x]), mp(INF, -1));

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == f ) continue;

		dfs1(p->to, x); st t = dp[p->to];

		t.fi.fi += p->dis, t.se.fi += p->dis;

		update(dp[x], t);

	}

}

void dfs2(int x, int f, st k) {

	update(dp[x], k);

	for(edge *p=adj[x];p;p=p->nxt) {

		if( p->to == f ) continue;

		st t = dp[x];

		t.fi.fi += p->dis, t.se.fi += p->dis;

		dfs2(p->to, x, t);

	}

}

int num[MAXN + 5];

int main() {

	int N; scanf("%d", &N);

	for(int i=1;i<=N;i++)

		scanf("%lld", &X[i]), fa[i] = i;

	for(int i=1;i<N;i++) {

		int u, v, w; scanf("%d%d%d", &u, &v, &w);

		addedge(u, v, w);

	}

	ll ans = 0;

	while( true ) {

		int cnt = 0;

		for(int i=1;i<=N;i++)

			if( fa[i] == i ) num[clr[i] = (++cnt)] = i;

		if( cnt == 1 ) break;

		for(int i=1;i<=N;i++)

			clr[i] = clr[find(i)];

		dfs1(1, 0), dfs2(1, 0, mp(mp(INF, -1), mp(INF, -1)));

		for(int i=1;i<=cnt;i++)

			lnk[i] = mp(INF, -1);

		for(int i=1;i<=N;i++) {

			if( dp[i].fi.se == clr[i] )

				lnk[clr[i]] = min(lnk[clr[i]], mp(dp[i].se.fi + X[i], dp[i].se.se));

			else lnk[clr[i]] = min(lnk[clr[i]], mp(dp[i].fi.fi + X[i], dp[i].fi.se));

		}

		for(int i=1;i<=cnt;i++)

			if( unite(num[i], num[lnk[i].se]) )

				ans += lnk[i].fi;

	}

	printf("%lld\n", ans);

}

@details@

被数据结构困住的我，用点分治 + 优先队列写了一个 prim。

然后它 MLE 了。

当时我就哭了。

咳咳。不过也算是增长了一点见识，同时还告诉我一个深刻的道理：不要被套路所困。不一定非得要数据结构才能维护的啊。

巴特西

@atcoder - CODE FESTIVAL 2017 Final - J@ Tree MST

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章