【BZOJ5252】林克卡特树(动态规划,凸优化)

题面

BZOJ(交不了)

洛谷

题解

这个东西显然是随着断开的越来越多,收益增长速度渐渐放慢。

所以可以凸优化。

考虑一个和\(k\)相关的\(dp\)

这个题目可以转换为在树上选择\(K\)条不相交的路径。

设\(f[i][0/1/2]\)表示当前点\(i\),这个点不和父亲连/和父亲连/在这里将两条链合并的最优值。

再记一维\(k\),表示子树中已经选了\(k\)条链。

这样子可以直接转移。

那么凸优化\(dp\),再额外记录一下最优解的链的最小值,就好了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 300300
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next,w;}e[MAX<<1];
int h[MAX],cnt=1;
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
ll sum;
int n,K;
struct Node{ll x;int y;}f[3][MAX],ans;
bool operator<(Node a,Node b){if(a.x!=b.x)return a.x<b.x;return a.y>b.y;}
Node operator+(Node a,Node b){return (Node){a.x+b.x,a.y+b.y};}
void cmax(Node &a,Node b){a=a<b?b:a;}
void dfs(int u,int ff,ll mid)
{
f[0][u]=(Node){0,0};
f[1][u]=(Node){-mid,1};
f[2][u]=(Node){-1ll<<60,0};
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(v==ff)continue;
dfs(v,u,mid);
Node tmp=max(f[0][v],max(f[1][v],f[2][v]));
cmax(f[2][u],f[2][u]+tmp);
cmax(f[2][u],f[1][u]+f[1][v]+(Node){e[i].w+mid,-1});
cmax(f[1][u],f[1][u]+tmp);
cmax(f[1][u],f[0][u]+f[1][v]+(Node){e[i].w,0});
cmax(f[1][u],f[0][u]+f[0][v]+(Node){-mid,1});
cmax(f[0][u],f[0][u]+tmp);
}
cmax(ans,max(f[0][u],max(f[1][u],f[2][u])));
}
int main()
{
n=read();K=read()+1;
for(int i=1;i<n;++i)
{
int u=read(),v=read(),w=read();
Add(u,v,w);Add(v,u,w);sum+=abs(w);
}
ll l=-sum,r=sum;
while(l<r)
{
ll mid=(l+r)>>1;
ans=(Node){-1ll<<60,0};dfs(1,0,mid);
if(ans.y>K)l=mid+1;
else r=mid;
}
ans=(Node){-1ll<<60,0};dfs(1,0,r);
printf("%lld\n",r*K+ans.x);
return 0;
}

最新文章

  1. js文件如何最后加载
  2. zencart産品描述加上錨文本
  3. android EditText光标位置(定位到最后)
  4. 警告 - no rule to process file &#39;WRP_CollectionView/README.md&#39; of type net.daringfireball.markdown for architecture i386
  5. 实验验证redis的快照和AOF
  6. 一个winform带你玩转rabbitMQ
  7. HDU2841 Visible Trees(容斥原理)
  8. Mac废纸篓 不能完全清空的有效解决方法
  9. 论文笔记之:RATM: RECURRENT ATTENTIVE TRACKING MODEL
  10. C++进制转换(十进制转二进制、八进制、随意进制)
  11. 1055: [HAOI2008]玩具取名 - BZOJ
  12. Java [Leetcode 104]Maximum Depth of Binary Tree
  13. c# winform textbox与combox让用户不能输入
  14. hdu 4293 dp求最大权值不重合区间
  15. linux FILE 类型.
  16. SQL中常用的时间格式
  17. Android基础知识巩固:关于PendingIntent和广播
  18. [转]探究java IO之FileInputStream类
  19. 转:java中Vector的使用
  20. iOS调用系统发送短信和邮件分享

热门文章

  1. 【转】新装的CentOS 7安装python3
  2. python简单计时器实现
  3. cnblogs客户端配置说明
  4. OpenGL学习笔记(4) GLM库的使用
  5. Laya 1.x 按文件夹TS代码合并
  6. 基于Vue的简单通用分页组件
  7. 快手hr面
  8. JVM类加载全过程--图解
  9. XML学习(一)
  10. 点斜杠 &amp; 如何查看linux程序安装位置 dpkg -L yyy