M_sea

洛谷1268 树的重量
传送门算法枚举+构造。不难发现,$M[i][j]$表示的就是i到j的最短路径。那么先建一颗$1-2$的树,然后把$...
扫描右侧二维码阅读全文
13
2017/11

洛谷1268 树的重量

传送门

算法

枚举+构造。

不难发现,$M[i][j]$表示的就是i到j的最短路径。

那么先建一颗$1-2$的树,然后把$3-n$依次加入。
对于第$i$个节点,枚举它之前的所有节点,使所有的非叶子节点尽可能地靠近叶子节点,远离根节点,使公共部分尽量多。

这话有点抽象,我们来具体看看。
画个图就能发现,把节点$i$设为$1-j$路径上分出来的点,则多出来的长度为$(d[1][i]+d[j][i]-d[1][j])/2$。
这个应该很好理解。

那么每次找一个最小的加入就好了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int g[50][50];
int main() {
    int n;
    do {
        n=read(); if (n==0) break;
        for (re int i=1;i<=n;i++)
            for (re int j=i+1;j<=n;j++)
                g[i][j]=g[j][i]=read();
        int ans=g[1][2];
        for (re int i=3;i<=n;i++) {
            int now=2147483647;
            for (re int j=1;j<i;j++)
                now=min(now,(g[1][i]+g[i][j]-g[1][j])/2);
            ans+=now;
        }
        printf("%d\n",ans);
    } while (n!=0);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 21 PM

发表评论