欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P1268 树的重量 图+贪心

程序员文章站 2022-05-30 08:27:52
...

洛谷 P1268 树的重量 图+贪心

题解:

(1)当n=2时,答案就是dis[1][2]。
(2)当n=3时,如下图:
洛谷 P1268 树的重量 图+贪心
树的权值为: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上呢?
答案是加入新产生的权值最小的那条边
洛谷 P1268 树的重量 图+贪心
因为如果不是最小的,那条红色的链就统计重复了。
(4)那么考虑n是任意值时,第n条路径可以处于1到2~(n-1)的任意一条路径上产生分支,那么我们显然要找最小值,因此最后答案:
ans=dis(1,2)+i=3nminj=2i1dis(1,i)+dis(j,i)dis(1,j)2ans=dis(1,2)+\sum_{i=3}^{n}{min_{j=2}^{i-1}\frac {dis(1,i)+dis(j,i)-dis(1,j)}{2}}

代码如下:

#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;
}
相关标签: