【每日一题】 4-3 Shortest Path
https://ac.nowcoder.com/acm/problem/13886
题意:
给一棵树，保证树的结点个数是偶数，定义点对的价值是他们的距离，求将这棵树分成 n/2 个点对之后，这些点对的最小价值。
解法：
贪心的考虑，我们希望使得一颗树内的点两两组合，这样代价会最小，如果这棵树的结点个数是偶数个的话，我们将他在树内的所有结点两两结合。否则，为了代价最小，我们选择子树的根节点向子树外连边，其他的偶数个结点连边，这样代价会最小。
所以答案就是所有奇数个数节点的子树的根节点到他爸爸的距离。就和树剖的dfs1一样，先求出子树的大小，然后判断是否是奇数即可一次dfs解决。
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e4 + 5;
struct edge
{
int to;
ll w;
int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init()
{
memset(head, -1, sizeof(head));
tot = 1;
}
void add(int a, int b, ll c)
{
e[tot] = edge{ b,c,head[a] };
head[a] = tot++;
}
int sz[MAXN];
ll ans;
void dfs(int u, int f)
{
sz[u] = 1;
for (int i = head[u]; i + 1; i = e[i].nex)
{
int to = e[i].to;
if (to == f)
continue;
dfs(to, u);
sz[u] += sz[to];
if (sz[to] & 1)
ans += e[i].w;
}
}
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ans = 0;
init();
int n;
sc("%d", &n);
for (int i = 1; i < n; i++)
{
int a, b; ll c;
sc("%d%d%lld", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dfs(1, 0);
pr("%lld\n", ans);
}
} 
Momenta公司福利 286人发布
查看6道真题和解析