UVa1668/LA6039 Let’s Go Green

2024-08-23 06:36

文章标签 go let green uva1668 la6039

本文主要是介绍UVa1668/LA6039 Let’s Go Green，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa1668/LA6039 Let’s Go Green

题目链接
题意
分析
AC 代码

题目链接

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

题意

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

分析

本题和最小路径覆盖问题看着很像，但最小路径覆盖问题是有向图且要求每个点只在一条路径上。本题和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;
}