洛谷 P1268 树的重量 图+贪心

洛谷 P1268 树的重量 图+贪心

题解：

（1）当n=2时，答案就是dis[1][2]。
（2）当n=3时，如下图：

树的权值为：dis(1,2) + 中间点到3的长度
中间点到3的长度=( dis(1,3) + dis(2,3) − dis(1,2) ) / 2
因此ans = dis(1,2) + ( dis(1,3) + dis(2,3) − dis(1,2) ) / 2
（3）在加入第四个点时，我们就需要决策一下到底是加在链1,2上呢？还是链1,3上呢？
答案是加入新产生的权值最小的那条边

因为如果不是最小的，那条红色的链就统计重复了。
（4）那么考虑n是任意值时，第n条路径可以处于1到2~(n-1)的任意一条路径上产生分支，那么我们显然要找最小值，因此最后答案：
$ans=dis(1,2)+\sum_{i=3}^{n}{min_{j=2}^{i-1}\frac {dis(1,i)+dis(j,i)-dis(1,j)}{2}}$ans=dis(1,2)+i=3∑n​minj=2i−1​2dis(1,i)+dis(j,i)−dis(1,j)​

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<map>
#define MAX 100005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,dis[35][35];
int main(){
    while(scanf("%d",&n)){
        if(n==0) break;
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                scanf("%d",&dis[i][j]);
            }
        }
        int ans=dis[1][2];
        for(int i=3;i<=n;i++){
            int tmp=INF;
            for(int j=2;j<i;j++){
                tmp=min(tmp,(dis[1][i]-dis[1][j]+dis[j][i])/2);
            }
            ans+=tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}