题解 P1268 【树的重量】

# 思路 考虑根据这个邻接矩阵，如何生成一棵树。 先将点$1-2$连边，并将距离算进最终答案，这样构成了一个只有两个节点的树。 见例图：（黑色为还未加入树中，　红色为加入了，　字母点为非叶子节点，数字点为叶子节点）  加入两个点$1-2$，最终答案加上($2 - Ａ - B - 1$)的长度  加入点$3$，最终答案再加上($A - C - D - 3$)的长度  加入点$4$，最终答案再加上($D - 4$)的长度  加入点$5$，最终答案加上($C - 5$)的长度  如此往复，最终加入全部的点  也就是每次加点的时候，只需要把它和最近的一个已经在树上的点相连即可。这条路径的长度需要加入最终答案。 难点在于，如何确定每次加点需要累计的答案。离当前待加入的点　最近的一个树中点一定不是一个叶子节点， 但是我们只有每个叶子节点之间的最短距离。 观察下图  $1 ,2$都已经在树中了，$3$不在树中，要在最终答案中加入$A - 3$的长度，可以发现： $$dis(A, 3) = (dis(2, 3) + dis(1, 3) - dis(1, 2)) / 2$$ 也就是我们枚举两个在树中的点对，通过上面的式子，得到加入这个点的价值，这些价值中取最小值即可。 这样就可以算出答案。 我们按顺序加入点，如果当前要加入的点为点$i$，那就要考虑每一个已加入的点$1$-$(i - 1)$组成的点对。 同时可以发现，只需要从枚举$1$到剩余其他树中的点即可。 # Codes 这题代码的话，我觉得唯一的难点在于如何读入…… ```cpp /*! * Copyright(c) 2019 Shu_Yu_Mo * MIT Licensed * Luogu: https://www.luogu.org/space/show?uid=44615 * Github: https://github.com/oldsuold/ * Gitee: https://gitee.com/Shu_Yu_Mo/ */ #include<cstdio> #include<cstring> #include<cmath> #include<cstring> #include<iostream> #include<cmath> #include<vector> #include<set> #include<algorithm> #define inf 0x7fffffff #define _R register using namespace std; const int _ = 110; inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; } int M[_][_]; int n; void doit() { memset(M, 0, sizeof(M)); for(_R int i = 1;i <= n;i++){ for(_R int j = 1;j <= n - i;j++){ M[i][j + i] = M[j + i][i] = read(); } } int ans = M[1][2]; for(_R int i = 3;i <= n;i++){ int TMP = inf; for(_R int j = 1;j < i;j++) TMP = min(TMP, ((M[1][i] + M[j][i] - M[1][j]) >> 1)); ans += TMP; } printf("%d\n", ans); } int main() { while((n = read()) != 0) doit(); return 0; } ```