题目描述

给出一棵树的叶子节点两两之间的距离,求这棵树的边权和。

题目分析

令a(i,j)为叶子i到j的距离
由于这是一棵树。
n=2的时候,只有一条链。

n=3的时候,由于是一棵树,所以3肯定连在1到2的那条链上,那么红边长=(a(1,3)+a(2,3)-a(1,2))/2

n=4的时候,4要么连在1到2的链上,要么连在1到3的链上(这样2到3的链已经包括在里面了),所以我们枚举并求最小新边权即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,ans;
int a[33][33];
int main(){
    int i,j;
    while(1){
        n=read();if(!n)break;
        for(i=1;i<=n;++i)
            for(j=i+1;j<=n;++j)
                a[i][j]=read(),a[j][i]=a[i][j];
        ans=a[1][2];
        for(i=3;i<=n;++i){
            int minn=INT_MAX;
            for(j=2;j<i;++j)
                minn=min(minn,(a[i][j]+a[1][i]-a[1][j])/2);
            ans+=minn;
        }
        printf("%d\n",ans);
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *