51nod 1737 配对【树形dp】

2019-11-08 01:51:17

字体：大中小

来源：转载

供稿：网友

题目：http://www.51nod.com/onlineJudge/questionCode.html#!PRoblemId=1737

题意：

给出一棵n个点的树，将这n个点两两配对，求所有可行的方案中配对两点间的距离的总和最大为多少。

分析：

贪心的想，为使距离总和最大，每条边乘上的系数就要尽量的大，设fx表示点x的儿子个数，那每一条边能乘上的最大的系数，就是：min(n−fx,fx) 这种贪心的方法是否存在于一种构造方法呢？构造：找出树的重心，只要保证删去重心后任意同一联通块中的两点不构成路径即可，这样每个连通块中的点都向其他连通块中的点连接，这样构造出来的配对方案满足了每条边都被统计min(s1,s2)次。（找重心是为了每个连通块不能超过n/2个点，其实只要最大连通块不超过n/2个点，就能构造出一种配对方案使得每条边被统计min(s1,s2)次。）时间复杂度O(n)

代码：

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 10;struct node { int v, w;};int n ;ll ans;vector <node> g[N];int dfs(int u, int pre) { int res = 1; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].v, w = g[u][i].w; if (v == pre) continue; int sonnum = dfs(v, u); ans += (ll)min(sonnum, n - sonnum) * w; res += sonnum; } return res;}int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); g[u].push_back((node) {v, w}); g[v].push_back((node) {u, w}); } ans = 0; dfs(1, -1); printf("%I64d/n", ans); return 0;}

上一篇：蓝桥杯算法训练 Lift and Throw

下一篇：集合