【NOIAC9】小h的树

Source and Judge

NOIAC9

Record

1h

Analysis

请先思考后再展开

这也是一道好题
把dp和树结构的性质等结合在了一起

找点性质:
因为要遍历每一个点,而且还是个树结构
不难发现每条边最多遍历2次

先考虑特殊情况,k=n
那么每条边都要遍历,而且“有点难发现”最后只被遍历一次的会是一条链
答案就是$2 \times 边总长-链长度$
所以为了答案最小,取直径……

然后推广一下,有些边可以不经过了
发现其实就是选取一个子树结构,让【上面说的值】最小
然后我们维护的东西是满足可加性的,只要保证一条链

接下来对于我来说有些难度,但可能对大佬来说是一个套路
就是搞一个树形dp,考虑直径的出现情况
因为满足可加性,设 $f(x,k,0/1/2)$ 表示在x的子树中选k个(根节点必选)
最后的下标,表示直径端点出现情况
然后在dp的过程中,枚举y,根据直径端点出现情况考虑x到y这条边的贡献情况

感觉这个dp状态的设计还是灰常关键的

最后要证明这个复杂度
方法灰常奇特啊
就是把枚举siz看做是枚举其子树内每个节点
那么对于每个点对,只会在其lca处被枚举到

Code

请先思考后再展开
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
const int INF=0x3f3f3f3f;
const int MAXN=3100;
int hou[MAXN];
int siz[MAXN];
struct Edge
{
int y,c,g;
}e[MAXN*2];
int ln=0;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=hou[x];hou[x]=ln;
}
int K;
int f[MAXN][MAXN][3];
//f[x>0][k][0/1/2]分别表示在x的子树选k个点(根节点必选)
//并且直径在其内部端点数为0、1、2时,选出的最小数结构花费
void dp(int x,int fa)
{
siz[x]=1;
f[x][1][0]=0;f[x][1][1]=0;f[x][1][2]=0;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dp(y,x);
for(int k1=mymin(K,siz[x]);k1>=1;k1--)
{
for(int k2=mymin(siz[y],K-k1);k2>=1;k2--)
{
f[x][k1+k2][0]=mymin(f[x][k1+k2][0],f[x][k1][0]+f[y][k2][0]+e[k].c*2);
f[x][k1+k2][1]=mymin(f[x][k1+k2][1],f[x][k1][1]+f[y][k2][0]+e[k].c*2);
f[x][k1+k2][1]=mymin(f[x][k1+k2][1],f[x][k1][0]+f[y][k2][1]+e[k].c);//向上
f[x][k1+k2][2]=mymin(f[x][k1+k2][2],f[x][k1][0]+f[y][k2][2]+e[k].c*2);
f[x][k1+k2][2]=mymin(f[x][k1+k2][2],f[x][k1][1]+f[y][k2][1]+e[k].c);//向左
f[x][k1+k2][2]=mymin(f[x][k1+k2][2],f[x][k1][2]+f[y][k2][0]+e[k].c*2);
}
}
siz[x]+=siz[y];
}
}
void main()
{
memset(f,63,sizeof f);
int n;scanf("%d%d",&n,&K);
for(int i=1;i<=n-1;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
dp(1,0);
int ans=INF;
for(int i=1;i<=n;i++) if(siz[i]>=K) ans=mymin(ans,f[i][K][2]);
printf("%d",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/f894.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%