bzoj4987(树形dp)

Posted on   |   In

题解

首先,$\sum_{i=1}^{k-1} dis(a_i,a_{i+1})​$ 最小化 那么对于这$k​$个点的选择可见必然是一个连通子树 可以反证 如何统计价值呢?我们考虑对于一棵树如何遍历每个点让路径和最小 显然是 $ 2sum-len​$ 即2倍路径和减去直径 这样子我们可以设$dp[i][j][0/1/2]​$ 表示在$i​$的子树中选了$j​$个点的联通子树 且直径的三种形态下的最小值 转移留给读者思考

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e3+10;
const double eps=1e-8;
#define ll long long
const ll inf=2e9;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int n,m,sz[MAXN];
ll dp[MAXN][MAXN][3];
ll ans;
int check(int x,int y){
    if(x==1&&y==1)return 1;
    else if(x==0&&y==1)return 1;
    return 2;
}

void dfs(int x,int pre){
    sz[x]=1;
    link(x){
	if(j->t==pre)continue;
	dfs(j->t,x);
	dec(i,min(sz[x],m),1)inc(k,0,2)for(int r=1;r+i<=m&&r<=sz[j->t];r++)inc(p,0,2-k){
	    dp[x][i+r][k+p]=min(dp[x][i+r][k+p],dp[j->t][r][p]+dp[x][i][k]+(j->v)*check(k,p));
	}
	sz[x]+=sz[j->t];
    }
    ans=min(ans,min(dp[x][m][1],dp[x][m][2]));
}

int main(){
    n=read();m=read();
    int x,y,z;
    inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    inc(i,1,n)inc(j,0,m)dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=inf;
    inc(i,1,n)dp[i][1][1]=dp[i][1][0]=0;
    ans=inf;
    dfs(1,0);
    printf("%lld\n",ans);
}

题目描述

从前有棵树。
找出$K$个点$A_1,A_2,…,A_k$。最小化$\sum_{i=1}^{k-1} dis(a_i,a_{i+1})$

输入描述

第一行两个正整数$n$,$k$,表示数的顶点数和需要选出的点个数。

接下来$n-1$行每行3个非负整数$x$,$y$,$z$，表示从存在一条从$x$到$y$权值为$z$的边

输出描述

一行一个整数，表示最小的距离和。