题解 P5866 【[SEERC2018]Space Station】

JK_LOVER · 2020-05-29 20:47:39 · 题解

写在前面的

在洛谷这么多题中，又找到一群还未开发的题。结合网上的题解，说说自己的看法。地址

题意

在一棵树上，求问从点 1 出发又回到点 1 的最小花费。其中可以选择两个端点跳跃，花费为 K 。但每条边要至少经历 1 次。

分析

• 先考虑没有跳跃的情况： ans=2\times\sum_i^{n-1} W_{e_i}
• 因为树上的简单路径有且只有一条。所以我们可以将路径转化为端点来考虑。 ans=2\times \sum_i^{n-1}W_{e_i} - \sum_j^{m}W_{e_j}+K\times m
• 因为每条路径至少要经历一次，所以我们选取的路径是要不重合的。对于一个树根来考虑。
• 如果子树中端点有偶数个，那么树根一定不在路径上。若有，则不满足每条路径至少经历一次。
• 所以子树端点为奇数时，则这条路径一定包含树根。

• 这样我们就可以写出方程：

  dp[u][i+j] = \min(dp[u][i+j],dp[u][i]+dp[v][j]+W_{e_i}) \ (j\&1=1) dp[u][i+j] = \min(dp[u][i+j],dp[u][i]+dp[v][j]+2\times W_{e_i}) \ (j\&1=0)

  代码就比较简单了。

  代码

  
  #include<bits/stdc++.h>
  using namespace std;
  int read()
  {
  int x=0,f=0;char ch=getchar();
  while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
  while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
  return f?-x:x;
  }
  const int N = 1010;
  int dp[N][N],n,m,k,ans,size[N],res[N];
  vector<int> G[N],W[N];
  void dfs(int u,int fa)
  {
  size[u] = 1;
  for(int i = 0;i < G[u].size();i++)
  {
      int v = G[u].at(i),w = W[u].at(i);
      if(v == fa) continue;
      dfs(v,u);
      memset(res,0x3f,sizeof(res));
  
      for(int j = 0;j <= size[u];j++)
      {
          for(int k = 0;k <= size[v];k++)
          {
              if(j+k > 2*m) continue;
              if(k&1)
              {
                  res[j+k] = min(res[j+k],dp[u][j]+dp[v][k]+w);
                  res[j+k+1] = min(res[j+k+1],dp[u][j]+dp[v][k]+w);
              }
              else 
              {
                  res[j+k] = min(res[j+k],dp[u][j]+dp[v][k]+2*w);
                  res[j+k+1] = min(res[j+k+1],dp[u][j]+dp[v][k]+2*w); 
              }
          }
      }
      size[u] += size[v];
      for(int j = 0;j <= size[u];j++) dp[u][j] = res[j];
  
  }
  }
  int main()
  {
  int T = read();
  while(T--)
  {   
      memset(dp,0,sizeof(dp));
      ans = 0;
      n = read();m = read();k = read();
      for(int i = 1;i <= n;i++) G[i].clear(),W[i].clear();
      for(int i = 1;i < n;i++)
      {
          int a = read(),b = read(),c = read();
          G[a].push_back(b);
          W[a].push_back(c);
          G[b].push_back(a);
          W[b].push_back(c);  
          ans += c+c;
      } 
      dfs(1,0);
      for(int i = 0;i <= min(2*m,n);i += 2)
      {
          ans = min(ans,dp[1][i] + (i/2)*k);
      }
      printf("%d\n",ans);
  }

}