P3354 河流

xuyiyan920 · 2020-10-30 20:54:59 · 个人记录

• 这题是一道树形dp题。因为必须要知道到伐木场的距离才可以求出花费，进行转移，所以这题的dp状态在原有的dp[i][j](i为当前结点，j为已选伐木场)上加一维，dp[i][j][k]为最小花费，j表示在i下游最近的伐木场。这样可以通过dp实现。

  ```cpp dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j],dp[now][0][s[m]][j-l]+dp[to][0][s[m]][l]); dp[now][1][s[m]][j]=min(dp[now][1][s[m]][j],dp[now][1][s[m]][j-l]+dp[to][0][now][l]); ```

• 这题dp初值应为0，然而这会影响第一轮的转移（不会被更新），所以应将

  dp[now][0][s[m]][j]+=dp[to][0][s[m]][0];
  dp[now][1][s[m]][j]+=dp[to][0][now][0];

  提至l的循环转移外，可以使第一轮转移正确。

• 在处理完当前结点后，应当对[0],[1]进行合并，因为这对下一步转移并没有影响，有影响的只是j。

  if(j>=1)
      dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j]+w[now]*(dis[now]-dis[s[m]]),dp[now][1][s[m]][j-1]);
  else
      dp[now][0][s[m]][0]+=w[now]*(dis[now]-dis[s[m]]);

• 还有注意[1]在之前转移时并没有算上当前i的伐木场，所以在这里需要从[j-1]转移过来，并对j进行特判，以免越界。

• 最后取dp[0][0][0][k]。

  #include <bits/stdc++.h>
  using namespace std;
  const int MAXN=100+10;
  struct node
  {
  int v,ne,w;
  };
  node t[MAXN<<1];
  int n,k,head[MAXN],w[MAXN],cnt,l,dp[MAXN][2][MAXN][MAXN],s[MAXN],hea,dis[MAXN];
  void build(int u,int v,int w)
  {
  t[++cnt].v=v,t[cnt].w=w;
  t[cnt].ne=head[u],head[u]=cnt;
  }
  void dfs(int now,int fa)
  {
  s[hea++]=now;
  for(int i=head[now];i;i=t[i].ne)
  {
      int to=t[i].v;
      if(to==fa)
          continue;
      dis[to]=dis[now]+t[i].w;
      dfs(to,now);
  }
  for(int i=head[now];i;i=t[i].ne)
  {
      int to=t[i].v;
      if(to==fa)
          continue;
      for(int m=0;m<hea;m++)
      {
          for(int j=k;j>=0;j--)
          {
              dp[now][0][s[m]][j]+=dp[to][0][s[m]][0];
              dp[now][1][s[m]][j]+=dp[to][0][now][0];
              for(int l=0;l<=j;l++)
              {
                  dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j],dp[now][0][s[m]][j-l]+dp[to][0][s[m]][l]);
                  dp[now][1][s[m]][j]=min(dp[now][1][s[m]][j],dp[now][1][s[m]][j-l]+dp[to][0][now][l]);
              }
          }
      }
  }
  for(int m=0;m<hea;m++)
  {
      for(int j=k;j>=0;j--)
      {
          if(j>=1)
              dp[now][0][s[m]][j]=min(dp[now][0][s[m]][j]+w[now]*(dis[now]-dis[s[m]]),dp[now][1][s[m]][j-1]);
          else
              dp[now][0][s[m]][0]+=w[now]*(dis[now]-dis[s[m]]);
      }
  }
  hea--;
  }
  int main()
  {
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {
      int vi,di;
      cin>>w[i]>>vi>>di;
      build(i,vi,di);
      build(vi,i,di);
  }
  dfs(0,-1);
  cout<<dp[0][0][0][k]<<endl;
  return 0;
  }