题目链接

  本题是2012年icpc亚洲区域赛雅加达(Jakarta)赛区的题目

题意

  输入一棵n（2≤n≤100000）个结点的树，每条边上都有一个权值。要求用最少的路径覆盖这些边，使得每条边被覆盖的次数等于它的权值，如下图所示。

分析

  本题和最小路径覆盖问题看着很像，但最小路径覆盖问题是有向图且要求每个点只在一条路径上。本题和UVa1664/LA6070 Conquer a New Region一个套路，表面是图论题，实际考的是数据结构——并查集。
  先分析本题的一个简单版本：如果树上只有一个点的度大于1，其余点的度都是1，最少的路径数是多少呢？计所有边权和为$s$，最大边权为$x$，思考一下可知最小路径数为$max(\lceil \frac{s}{2}\rceil ,x)$。
  现在解题思路就有了：考虑每个点$i$关联的所有边，权和为$s_i$，最大边权为$x_i$，则其关联边构成的子图最小路径数为$c_i=max(\lceil \frac{s_i}{2}\rceil ,x_i)$。枚举每条边$(u,v,w)$，用并查集将两端点各自关联的所有边子图依次合并就可以得出答案，$u,v$合并的子图最小路径数为$c_u+c_v-w$。

AC 代码

#include <iostream>
using namespace std;#define N 100010
int u[N], v[N], w[N], x[N], s[N], f[N], n;int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);
}int solve() {cin >> n;for (int i=1; i<=n; ++i) x[i] = s[i] = 0, f[i] = i;for (int i=1; i<n; ++i) {cin >> u[i] >> v[i] >> w[i]; s[u[i]] += w[i]; s[v[i]] += w[i];x[u[i]] = max(x[u[i]], w[i]); x[v[i]] = max(x[v[i]], w[i]);}for (int i=1; i<=n; ++i) s[i] = max(x[i], (s[i]+1) >> 1);int cc = 0;for (int i=1; i<n; ++i) {int x = find(u[i]), y = find(v[i]); f[x] = y; cc = s[y] += s[x] - w[i];}return cc;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t; cin >> t;for (int k=1; k<=t; ++k) cout << "Case #" << k << ": " << solve() << endl;return 0;
}