题目大意

　　给出一棵树上每两个叶子节点之间的距离，求树的总边权和。

题解

　　定义节点a到b的简单路径长度为[a,b]，树中节点c要到达路径[a,b]所要经过的距离为dist(c, [a,b])，在树中，与节点c相连的边的边权为e(c)。

　　显然画个图或列个方程就可以知道dist(c, [a,b]) = ([a,c] + [b,c] - [a,b])/2，假设我们已经把1至i个节点加入到树中，此时再加入一个节点d，树所增加的重量便是e(d)。怎么求呢？我们假设正确的做法就是把d用一条边与树相连，设交点为u。对于树上原有的i个点，任意选出两个点x,y，如果u在[x,y]上，则dist(d, [x,y]) = e(d)。如果u不在[x,y]上，则dist(d, [x,y]) = e(d) + dist(u, [x,y])。因此e(d)=min{d, [x,y]}。所以一个一个叶子节点往树里插即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX_N = 50, INF = 0x3f3f3f3f;

int Dist[MAX_N][MAX_N];

int main()

{

    int n;

    while (scanf("%d", &n) && n)

    {

        for (int i = 1; i <= n; i++)

            for (int j = i + 1; j <= n; j++)

                scanf("%d", &Dist[i][j]);

        int ans = Dist[1][2];

        for (int i = 3; i <= n; i++)

        {

            int eLen = INF;

            for (int j = 1; j <= i - 1; j++)

                for (int k = j + 1; k <= i - 1; k++)

                    eLen = min(eLen, (Dist[j][i] + Dist[k][i] - Dist[j][k]) / 2);

            ans += eLen;

        }

        printf("%d\n", ans);

    }

}

巴特西

luogu1268 树的重量

题目大意

题解

最新文章

热门文章