文档章节

BZOJ5252 八省联考2018林克卡特树(动态规划+wqs二分)

o
 osc_4nmshwhm
发布于 2018/08/07 01:53
字数 1211
阅读 0
收藏 0

  假设已经linkcut完了树,答案显然是树的直径。那么考虑这条直径在原树中是怎样的。容易想到其是由原树中恰好k+1条点不相交的链(包括单个点)拼接而成的。因为这样的链显然可以通过linkcut拼接起来,而若选择不超过k条链则可能有链不得不被cut拆开,即使不会被拆开也可以通过选择单点来达到恰好k+1条(下设k=k+1)。

  那么问题变为在树上选择k条点不相交的链使边权和最大。最简单的dp就是设f[i][j]为i子树中选j条链的最大权值,且用一维012状态记录i这个点在子树中的度数,转移类似于一个树形背包。复杂度看起来是O(nk^2),实际上似乎是O(nk),可以拿60分。

  然而再往上即使复杂度去一个k也没有更高的分了。这暗示我们可以做到与k无关的复杂度。

  考虑去掉k的限制。这样仍然是一个dp,只是去掉了一维,复杂度变为O(n)。注意一些细节,比如说仅选择单点看做度数为1,按照210的顺序更新等等。

  k怎么办?考虑wqs二分,也叫凸优化、带权二分啥的。我们把选择x条链的代价设为x*cost。可以发现,如果把cost设成-inf,那么会选择n条链;如果设成inf,会选择0条链;而随着cost从-inf增加到inf,最优链数感觉上应该是单调不增的。那么我们可以二分cost,使得链数最终在k处停止,这个时候肯定求得了选k条链的最优方案,于是再补回cost就可以求得最优解了。至于这个东西是不是单调不增的呢?貌似是的。为什么呢?大胆猜想不用证明感觉一个东西便宜的时候都不买,涨价了更没有理由买啊。证明我也不懂。

  dp的时候记录一下最优的时候至少需要选择几条链。因为cost可能与一段链数对应,有可能无法刚好二分到选了k条链,不过这说明他们在该情况下都能作为最优解,则他们的加权(x*cost)答案相同。那么只要能够二分到这种加权答案就可以算出来k条链的答案了。于是保留选择的链数最接近k而又不超过k的答案,最终答案加上k*cost。

  还有一个细节,cost只需要在整数范围内二分就可以了。具体还是用坐标系来理解吧,链数对应的实际答案构成一个凸壳,用斜率为cost的直线去切这个凸壳,第一个碰上的点就是我们找到的答案。因为其中都是整点,用整数的斜率去切就可以了。但其实我也不知道我在说啥。

  “题目并不难。”

 

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 300010
#define ll long long
#define inf 300000000010
#define max(a,b) (((a)>(b))?(a):(b))
int n,k,p[N],t=0;
ll ans;
struct data2
{
    ll x;int cnt;
    bool operator >(const data2&a) const
    {
        return x>a.x||x==a.x&&cnt<a.cnt;
    }
    data2 operator +(const data2&a) const
    {
        return (data2){x+a.x,cnt+a.cnt};
    }
    data2 operator -(const data2&a) const
    {
        return (data2){x-a.x,cnt-a.cnt};
    }
}f[N][3];
struct data{int to,nxt,len;
}edge[N<<1];
void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}
void dfs(int k,int from,ll cost)
{
    f[k][0]=(data2){0,0};f[k][1]=(data2){-cost,1};f[k][2]=(data2){-inf,0};
    for (int i=p[k];i;i=edge[i].nxt)
    if (edge[i].to!=from)
    {
        int y=edge[i].to;
        dfs(y,k,cost);
        data2 w=max(f[y][0],max(f[y][1],f[y][2]));
        data2 u=f[y][1]+(data2){edge[i].len+cost,-1},v=f[y][0]+(data2){edge[i].len,0};
        f[k][2]=max(f[k][2]+w,f[k][1]+max(u,v));
        u=f[y][1]+(data2){edge[i].len,0},v=f[y][0]+(data2){edge[i].len-cost,1};
        f[k][1]=max(f[k][1]+w,f[k][0]+max(u,v));
        f[k][0]=f[k][0]+w;
    }
    
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj5252.in","r",stdin);
    freopen("bzoj5252.out","w",stdout);
    const char LL[]="%I64d";
#else
    const char LL[]="%lld";
#endif
    n=read(),k=read()+1;
    for (int i=1;i<n;i++)
    {
        int x=read(),y=read(),z=read();
        addedge(x,y,z),addedge(y,x,z);
    }
    ll l=-inf,r=inf;
    while (l<=r)
    {
        ll mid=l+r>>1;
        dfs(1,1,mid);
        if (max(f[1][0],max(f[1][1],f[1][2])).cnt<=k) ans=max(f[1][0],max(f[1][1],f[1][2])).x+k*mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

VMware——在CentOS中安装VMware Tools

VMware——在CentOS中安装VMware Tools 摘要:本文主要记录了如何在VMware中的CentOS系统中,安装VMware Tools。 安装依赖 查看系统相关信息: 1 [root@localhost ~]# uname -r2 3.10.0-32...

osc_5h5udyht
9分钟前
5
0
SpringCache分布式缓存学习

Spring Cache 简介 Cache接口为缓存的组件规范定义,包含缓存的各种操作集合 Cache接口下Spring提供了各种xxcache的实现;如RedisCache,EhCacheCache,ConcurrentMapCache等; 每次调用需要缓...

osc_4dgu16li
11分钟前
7
0
Python全栈之Flask 简介

前言 Python Web框架里比较有名当属Django,Django功能全面,它提供一站式解决方案,集成了MVT(Model-View-Template)和ORM,以及后台管理。但是缺点也很明显,它偏重。就像是一个装潢好的房...

osc_15fvklrg
12分钟前
5
0
WEB攻击手段及防御第2篇-SQL注入

概念 SQL注入即通过WEB表单域插入非法SQL命令,当服务器端构造SQL时采用拼接形式,非法SQL与正常SQL一并构造并在数据库中执行。 简单的SQL注入的例子: 例1:test123456 or 1=1; 加上or 1=1,...

osc_4hct2n4z
13分钟前
5
0
java 反射机制 (获取父类泛型的类型)getGenericSuperclass

https://blog.csdn.net/jidetashuo/article/details/53538231

Java搬砖工程师
13分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部