本文主要是介绍UVa1668/LA6039 Let’s Go Green,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
UVa1668/LA6039 Let’s Go Green
- 题目链接
- 题意
- 分析
- AC 代码
题目链接
本题是2012年icpc亚洲区域赛雅加达(Jakarta)赛区的题目
题意
输入一棵n(2≤n≤100000)个结点的树,每条边上都有一个权值。要求用最少的路径覆盖这些边,使得每条边被覆盖的次数等于它的权值,如下图所示。
分析
本题和最小路径覆盖问题看着很像,但最小路径覆盖问题是有向图且要求每个点只在一条路径上。本题和UVa1664/LA6070 Conquer a New Region一个套路,表面是图论题,实际考的是数据结构——并查集。
先分析本题的一个简单版本:如果树上只有一个点的度大于1,其余点的度都是1,最少的路径数是多少呢?计所有边权和为 s s s,最大边权为 x x x,思考一下可知最小路径数为 m a x ( ⌈ s 2 ⌉ , x ) max(\lceil \frac s 2 \rceil,x) max(⌈2s⌉,x)。
现在解题思路就有了:考虑每个点 i i i关联的所有边,权和为 s i s_i si,最大边权为 x i x_i xi,则其关联边构成的子图最小路径数为 c i = m a x ( ⌈ s i 2 ⌉ , x i ) c_i=max(\lceil \frac {s_i} 2 \rceil,x_i) ci=max(⌈2si⌉,xi)。枚举每条边 ( u , v , w ) (u,v,w) (u,v,w),用并查集将两端点各自关联的所有边子图依次合并就可以得出答案, u , v u,v u,v合并的子图最小路径数为 c u + c v − w c_u+c_v-w cu+cv−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;
}
这篇关于UVa1668/LA6039 Let’s Go Green的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!