BZOJ_4987_Tree_树形DP
2024-09-04 15:53:51
BZOJ_4987_Tree_树形DP
Description
从前有棵树。
找出K个点A1,A2,…,Ak。
使得∑dis(AiAi+1),(1<=i<=K-1)最小。
Input
第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。
接下来n-l行每行3个非负整数x,y,z,表示从存在一条从x到y权值为z的边。
I<=k<=n。
l<x,y<=n
1<=z<=10^5
n <= 3000
Output
一行一个整数,表示最小的距离和。
Sample Input
10 7
1 2 35129
2 3 42976
3 4 24497
2 5 83165
1 6 4748
5 7 38311
4 8 70052
3 9 3561
8 10 80238
1 2 35129
2 3 42976
3 4 24497
2 5 83165
1 6 4748
5 7 38311
4 8 70052
3 9 3561
8 10 80238
Sample Output
184524
考场上写了个贪心的树形背包水了50分。
说真的这状态其实好简单的不知道为什么没想到。
可以发现选的一定是一个连通块。
在一个连通块内的走法肯定是沿着直径的一个端点走向另一个端点,中间经过剩余的点。
这样代价是总边权*2-直径长度。
设f[i][j][k]表示i的子树内选了j个点,其中子树里有k个点是直径的端点(k<=2)。
转移的话很简单,考虑父亲到儿子连的这条边对答案贡献几次即可。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 3050
#define _min(x,y) ((x)<(y)?(x):(y))
int head[N],to[N<<1],nxt[N<<1],val[N<<1],n,cnt,K,f[N][N][3],a[N];
int ans=1<<30,siz[N];
inline void add(int u,int v,int w) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void upd(int &x,int y) {if(x>y) x=y;}
void dp(int x,int y) {
int i,j,k; siz[x]=1;
f[x][1][0]=f[x][1][1]=0;
for(i=head[x];i;i=nxt[i]) {
if(to[i]!=y) {
dp(to[i],x);
for(j=siz[x];j;j--) {
for(k=siz[to[i]];k;k--) {
int w=val[i],w2=w<<1;
upd(f[x][j+k][0],f[x][j][0]+f[to[i]][k][0]+w2);
upd(f[x][j+k][1],f[x][j][0]+f[to[i]][k][1]+w);
upd(f[x][j+k][1],f[x][j][1]+f[to[i]][k][0]+w2);
upd(f[x][j+k][2],f[x][j][0]+f[to[i]][k][2]+w2);
upd(f[x][j+k][2],f[x][j][1]+f[to[i]][k][1]+w);
upd(f[x][j+k][2],f[x][j][2]+f[to[i]][k][0]+w2);
}
}
siz[x]+=siz[to[i]];
}
}
ans=min(ans,f[x][K][2]);
}
int main() {
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&K);
int i,x,y,z;
for(i=1;i<n;i++) {
scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
}
dp(1,0);
printf("%d\n",ans);
}
最新文章
- BizTalk动手实验(十五)AS2消息安全传输
- .scss写法及如何转化为.css
- hdu 5412 CRB and Queries
- [HDOJ5510]Bazinga(并查集)
- 【系统Configmachine.config与自己的应用程序的App.config/Web.Config配置节点重复】解决方法
- 基础数据结构 之 栈(python实现)
- Maven配置jar(war)包自动打包上传Maven服务器的配置
- VS2010的openssl源码编译方法
- css-网页整体css布局
- ChromiumFX中js调用C#方法
- WebSite---前台系统图片验证码心得
- eslint 的基本配置介绍
- redis Lua学习与坑
- 【golang-GUI开发】qt之signal和slot(二)
- 泛型-----键值对----映射 hashmap--entry中key value 链表
- Java之";instanceof";和";isInstance";代码举例
- scrapy中自动补全url
- FortiGate 硬件加速
- HDU 5715 XOR 游戏 二分+字典树
- jQuery常用属性方法大全 attr(),val()
热门文章
- php的strip_tags,htmlspecialchars,htmlentities,stripslashes,addslashes解释
- scikit-learn(project中用的相对较多的模型介绍):2.3. Clustering(可用于特征的无监督降维)
- 在Mac OS X中下载Android源代码的一些经验
- java 中的final
- golang截取字符串
- 浅谈WPF本质中的数据和行为
- Redis实现主从复制(转)
- VS2013 自动添加头部注释 -C#开发
- hadoop 小文件 挂载 小文件对NameNode的内存消耗 HDFS小文件解决方案 客户端 自身机制 HDFS把块默认复制3次至3个不同节点。
- StackOver上的一个wx刷新显示的例子