题解 P3354 [IOI2005]Riv 河流

slgdsxw · 2020-07-16 16:06:34 · 题解

怎么没有wqs二分的题解……

树形dp的做法就不多赘述了， f(i,j,k) 表示点 i 下游第一个伐木场在点 j ， i 和其子树内建 k 个伐木场时，点 i 和其子树内的木材运至伐木场的最小代价。理论复杂度 O(nk^2) ，细节处理不好容易被链卡到 O(nk^3) , 注意事项在代码中有注释。

题目要求恰选择 k 个伐木场，可以意会到随着选的伐木场个数的增加，代价的减少的速度在降低 (凸性），考虑使用wqs二分解决。我们去掉树形dp的第三维的个数限制，并给每个伐木场的建立附加 C 的代价， dp时记录建立的伐木场数，据此调整 C 的大小。特别的，无论 C 是多少，当前建立的伐木场数恰等于 k 的时候可以直接退出二分，因为建立伐木场数一定时最小代价显然一定。复杂度 O(n^2loga) ，a指最大可能的答案（所有的木料流到 bytetown 的运费）。

关于wqs二分实现的个人建议：

取值（如分段数，此题即建伐木场数）最大/小化，方便考虑二分范围的转移
答案的计算、dp的细节、二分范围都跟取值的最大/小化的选择相适应
有些数据导致最终二分出来的阙值分的段数多/少，考虑到分的段数固定，答案的最值唯一，当前段数等于所需段数时直接退出二分取当前值，速度和正确性都有保障。阙值需要小数才能分段正确的情况尽量通过 1 避免。

代码如下（细节在注释中）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105,inf=0x3f3f3f3f;
int n,k,cnt,top;
int head[N],c[N],fa[N],len[N],dep[N],st[N];
struct edge
{
    int to,nxt;
}pl[N*2];
void add(int u,int v)
{
    pl[++cnt].nxt=head[u];
    pl[cnt].to=v;
    head[u]=cnt;
}
struct wqs
{
    int mid,ansv,sumf;
    int f[N][N],g[N][N];
    void dfs(int u)
    {
        int v;
        sumf+=c[u]*dep[u];
        for(int i=head[u];i;i=pl[i].nxt)
        {
            v=pl[i].to;
            if(v==fa[u])continue;
            dep[v]=dep[u]+len[v];
            dfs(v);
        }
    }
    void dp(int u)
    {
        int v;
        st[++top]=u;
        for(int i=1;i<=top;i++)f[u][st[i]]=g[u][st[i]]=0;//注意初始化 
        for(int i=head[u];i;i=pl[i].nxt)
        {
            v=pl[i].to;
            if(v==fa[u])continue;
            dp(v);
            for(int j=1;j<=top;j++)
            {
                f[u][st[j]]+=f[v][st[j]];
                g[u][st[j]]+=g[v][st[j]];
            }
        }
        f[u][u]+=mid;g[u][u]++;//用祖先是自己代表该点建伐木场的情况 
        for(int i=1;i<=top;i++)
        {
            f[u][st[i]]+=c[u]*(dep[u]-dep[st[i]]);
            if(f[u][u]<=f[u][st[i]])f[u][st[i]]=f[u][u],g[u][st[i]]=g[u][u];//小于等于号表示了在代价最少时尽可能多建伐木场 
        }
        top--;
    }
    void solve()
    {
        k++;// 先选上 bytetown
        sumf=0;
        dfs(0);
        int l=0,r=sumf;
        while(l<=r)
        {
            mid=(l+r)>>1;
            dp(0);
            if(g[0][0]>=k)ansv=mid;//尽可能多选后大于等于 k，说明可能调整到 k ，记录答案 
            if(g[0][0]==k)break;
            if(g[0][0]>k)l=mid+1;
            else r=mid-1;
        }
        mid=ansv;dp(0);
        //cout<<ansv<<endl;
        cout<<f[0][0]-k*mid;//最终答案减去附加的代价 
    }
}s1;
struct treedp// 这里我们的第二维 j 表示 祖先是 st[j] ,f[u][u][k] 表示 u 建伐木场 ，除 u 外还建了 k 个伐木场 
{
    int siz[N],f[N][N][N];
    void solve()
    {
        dp(0);
        cout<<f[0][1][k];
    }
    void dp(int u)
    {
        int v;
        st[++top]=u;
        siz[u]=1;
        for(int i=head[u];i;i=pl[i].nxt)
        {
            v=pl[i].to;
            if(v==fa[u])continue;
            dep[v]=dep[u]+len[v];
            dp(v);
            for(int j=1;j<=top;j++)
            {
                for(int t=min(siz[u]+siz[v],k);t>=0;t--)
                {
                    f[u][j][t]+=f[v][j][0];//因为 f 的初值都是 0 ，先选一个状态强制转移在取 min 
                    for(int l=max(1,t-siz[u]);l<=min(siz[v],t);l++)// 此时 siz[u] 表示 v 之前的子树大小和 ，第三维大于siz[u] 的状态还未计算无意义 
                        f[u][j][t]=min(f[u][j][t],f[u][j][t-l]+f[v][j][l]);//因此 t-l<=siz[u] ，即 l>=t-siz[u] ,不注意这里会被链卡到更劣的复杂度 
                }
            }
            siz[u]+=siz[v];
        }   
        for(int i=top;i>=1;i--)
            for(int j=0;j<=min(siz[u],k);j++)
            {
                f[u][i][j]+=c[u]*(dep[u]-dep[st[i]]);
                if(j>=1)f[u][i][j]=min(f[u][i][j],f[u][top][j-1]); 
            }
        top--;
    }
}s2;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>fa[i]>>len[i];
        add(fa[i],i);
    }
    s2.solve();
    return 0;
}