HDU 5815 - Golden Week

时间：2024-11-27 13:03:38

题意：

　　王国地图为 n 个节点的根树，首都为 1，

　　m 个旅行家要去不同的终点旅游，他们分别有各自的预算，如果路上总费用超过预算就不去了

　　给每条路定价， 让赚的钱最多

分析：

　   DP[i][j]表示当从首都到城市i的路径花费为j时，以i为根的子树中的点作为目的城市的旅行者的最大花费.

　　只需要考虑j值等于0或等于某位旅行者预算的情况，所以dp的状态数是O(NM)的.

　　状态转移方程式：

　　DP[i][j] = j* n(i,j) + ∑​max(DP[k][j​i]) (ji >= j)
　　　　

　　　　( n(i,j)为以i作为目标城市且预算不小于j的旅行者数量，

　　　　  k 为 i 的所有子代节点

　　　　  ​max(DP[k][j​i]) 为节点k的所有ji >= j 的 DP[k][j​i] 的最大值 )

　　上式max(DP[k, j​i]) (ji >= j) 可用 DP[i][j] = max(DP[i][j], DP[i][j+1]) 递推而得
则转移方程式为：

DP[i][j] = j* n(i,j) + DP[i][j].

　　确定完每一点的最大花费总和后，两点的最大花费总和相减即为该边的定价

　　注意起点的花费一定为 0 ！

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <algorithm>

 using namespace std;

 #define LL long long

 const int MAXN = ;

 int t, n, m, s;

 vector<int> mp[MAXN], id[MAXN];

 LL dp[MAXN][MAXN];

 LL v[MAXN];

 int edge[MAXN][MAXN];

 int bst[MAXN][MAXN];

 LL ans[MAXN];

 LL a[MAXN];

 void DFS(int x,int fa)

 {

     for (int i = ; i < mp[x].size(); i++)

     {

         if (mp[x][i] != fa) DFS(mp[x][i], x);

     }

     for (int j = s-; j >= ; j--)

     {

         int t = ;

         for (int i = ; i < id[x].size(); i++)

             if (a[id[x][i]] >= v[j]) t++;

         dp[x][j] += t*v[j];                         //j* n(i,j)

         for (int i = ; i < mp[x].size(); i++)

         {

             if (mp[x][i] == fa) continue;

             int p = mp[x][i];

             dp[x][j] += dp[p][j];

         }

         if (j == s- || dp[x][j+] <= dp[x][j])

         {

             bst[x][j] = j;

         }

         else

         {

             dp[x][j] = dp[x][j+];

             bst[x][j] = bst[x][j+];

         }

     }

 }

 void DFS2(int x,int a,int fa)

 {

     for (int i = ; i < mp[x].size(); i++)

     {

         int e = mp[x][i];

         if (e == fa) continue;

         int b = bst[e][a];

         ans[edge[x][e]] =v[b]- v[a];

         DFS2(e,b,x);

     }

 }

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &m);

         for (int i = ; i <= n; i++) mp[i].clear(), id[i].clear();

         memset(dp,,sizeof(dp));

         for (int i = ; i < n ;i++)

         {

             int u,v; scanf("%d%d", &u, &v);

             mp[u].push_back(v);

             mp[v].push_back(u);

             edge[u][v] = edge[v][u] = i;

         }

         for (int i = ; i <= m; i++)

         {

             int u; scanf("%d%lld",&u, &a[i]);

             v[i] = a[i];

             id[u].push_back(i);

         }

         id[].clear();//起始点不计费!

         v[] = ;

         sort(v,v++m);

         s = unique(v,v++m) - v;

         DFS(,-);

         DFS2(,,-);

         printf("%lld\n",dp[][]);

         for (int i = ; i < n-; i++)

             printf("%lld ",ans[i]);

         printf("%lld\n", ans[n-]);

     }

 }

相关文章