【每日一题】Shortest Path
Shortest Path
https://ac.nowcoder.com/acm/problem/13886
题目
题目描述： 今天，HH成为一名设计师，他面临一个问题，因此他要求您提供帮助。
Treeisland是一个拥有n个城市和n-1条双向道路的国家，您可以从任何城市前往任何其他城市。
设计人员将设计一个计划，将n个城市分为n / 2对，以使n / 2对城市之间的长度之和最小。
现在，HH已完成它，但他不知道这是否正确，因此他想和您一起计算。
保证n为偶数。
第一行包含一个正整数T（1≤T≤100），表示有T个测试用例。
对于每个测试的情况：第一行包含一个正整数n（1≤n≤10 4），代表城市在Treeisland数，它的保证n是偶数。
然后跟随n-1行。每行有三个正整数U，V和Len，（U≠V，1≤u≤n，1≤v≤n，1≤len≤109 指示存在u和v之间len个长度的道路）。
这保证您可以从任何城市到达任何城市。
对于每个测试用例，一行输出一个整数，代表最小长度之和。
解析
这道题没有复杂的算法，只是单纯的dfs，但是需要思考。
- 我们先来简单描述一下这道题：我们每两个点组成一组，取得他们之间的长度。最后求最短长度总和。
算法讲解：
- 刚看到的时候，我觉得无从下手，因为又是一道求啥最短长度和的题目，吓到我人都懵掉了。看到邓老师讲解后豁然开朗。
- 我们要取得最短长度的话，我们就要尽量不重复选边（重复会造成资源浪费）。
就像这个，你不选左边的，硬是要选右边的岂不是有点毛病。 - 所以在不重复选边的思考下，我们发现，每条边只有两种可能：选或不选！那么我们只要知道某条边什么时候选就行了。
由这点我们就发现，我们不管怎么选边都没事，最后的边和一定的。 - 那么我们对着某一个节点来考虑这个问题：某一个节点的选择一般都是最近的节点（父节点），或者在已占用的情况下找一个远一点的（兄弟节点）。
- 但是为什么是父节点和兄弟节点呢？让我们来看下面这张图：
- 在这张图里面我们可以发现：左边三个节点无法内部消化，兄弟可以配在一起（父节点可以找前面的）。而四个节点的可以直接成双内部消化了。
- 所以我们得到的结论就是：当子树为奇数的时候，根节点一定会和前面的点相连（对叶节点同样适用，叶节点是奇数树，而且一定连边）。
操作方法：
- 知道算法后，操作就是其次比较难的地方了。在这个dfs里面我们要先明确我们的工作是什么。
- <1>我们要知道以某一点为根节点的子树大小（用于判断是否可内部消化）。<2>我们要得到我们的最小权和。
- 首先计算子树大小，我们在这里运用分治递归的思路，从小到大进行合并：我们用一个变量（cnt）累加根节点的每一条支路的节点数。
- 然后就是得到最小权和：我们可以在递归的时候添加一个变量用于保存当前路径（当前根节点和其父节点）的权值，是奇数就加上就好了（原因见算法讲解）。
打代码咯：
- 首先是老操作，前向星保存树形结构。
- 然后就可以进行我们惊险刺激的dfs了，这里唯一要注意的就是我们没有确定的根，随便选一个就好了（权值为啥都一样，反正总数是偶数也不用在意，我们还是填0）。
- 看代码吧~
AC代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
//代码预处理区
const int MAX = 1e5 + 7;
int head[MAX], tot;
struct Node {
int v, w, next;
} edge[MAX << 1];
ll ans;
//全局变量区
template<class T>inline void read(T& res);
void add_edge(int u, int v, int w);
int dfs(int u, int fa, int w);
//函数预定义区
int main() {
int T; read(T);
while (T--) {
int n; read(n);
tot = 0; memset(head, 0, sizeof head);
for (int i = 1; i <= n - 1; i++) {
int u, v, w; read(u); read(v); read(w);
add_edge(u, v, w);
add_edge(v, u, w);
}
ans = 0;
dfs(1, 0, 0);
printf("%lld\n", ans);
}
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
void add_edge(int u, int v, int w) {
tot++;
edge[tot].v = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot;
}
int dfs(int u, int fa, int w) {
int cnt = 1;//初始化为1表示计算自己这个点
for (int i = head[u]; i; i = edge[i].next)
if (edge[i].v != fa)
cnt += dfs(edge[i].v, u, edge[i].w);
//计算子树的总节点数
if (cnt & 1) ans += w;
//当前树节点为奇数则要加上与父节点的连接
return cnt;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
查看5道真题和解析
