HDU 4003 Find Metal Mineral

这个题是POJ1849的加强版。

先说一个很重要的结论，下面两种方法都是从这个结论出发的。

一个人从起点遍历一颗树，如果最终要回到起点，走过的最小权值就是整棵树的权值的2倍。

而且K个人的情况也是如此，大不了只有一个人走，其他K-1个人待着不动就行了。

而题目中说了这些人不比回到原点，所以就想办法考虑哪些多走的路程，最后用整棵树权值2倍减去就好了。

一、

多数人的做法是分组背包，推荐这篇博客。

里面的状态的定义并不复杂，和网上那些千篇一律的做法比，思路很新颖。

f(i, j)表示i为根的子树有j个机器人出发，遍历这棵子树可以少走多少路。

最终答案为sum - f(S, K)

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int maxk = ;

 int n, s, k;

 vector<int> G[maxn], C[maxn];

 int f[maxn][maxk];

 void DP(int u, int fa)

 {

     for(int i = ; i < G[u].size(); i++)

     {

         int v = G[u][i], w = C[u][i];

         if(v == fa) continue;

         DP(v, u);

         for(int i = k; i >= ; i--)

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

                 f[u][i] = max(f[u][i], f[u][i-j] + f[v][j] + ( - j) * w);

     }

 }

 int main()

 {

     while(scanf("%d%d%d", &n, &s, &k) == )

     {

         for(int i = ; i <= n; i++) { G[i].clear(); C[i].clear(); }

         int sum = ;

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

         {

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

             sum += w;

             G[u].push_back(v); C[u].push_back(w);

             G[v].push_back(u); C[v].push_back(w);

         }

         sum <<= ;

         memset(f, , sizeof(f));

         DP(s, );

         printf("%d\n", sum - f[s][k]);

     }

     return ;

 }

代码君

二、

这篇博客中

还有一种更为巧妙的做法，就是每次从起点出发找到一条最长的路径，记录下路径的长度，然后把这条路径上边的权值变为相反数。注意，已经变为负权的边就不再变回去了。

这样找K次最长的路径，然后加起来就是可以最多少走多少路。

为什么要把权值变成负的，因为你第二次第三次再走这条路的时候，就表示少走了负的权值，也就是多走了。如果出现所有的路都是负权的情况，那么树中最长路的路径就是0，也就是机器人原地不动。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int maxn =  + ;

 struct Edge

 {

     int u, v, w;

     Edge(int u, int v, int w):u(u), v(v), w(w) {}

 };

 vector<Edge> edges;

 vector<int> G[maxn];

 void AddEdge(int u, int v, int w)

 {

     edges.push_back(Edge(u, v, w));

     edges.push_back(Edge(v, u, w));

     int m = edges.size();

     G[u].push_back(m - );

     G[v].push_back(m - );

 }

 int n, s, k;

 int len, id;

 int pre[maxn];

 void dfs(int u, int fa, int d)

 {

     if(d > len) { len = d; id = u; }

     for(int i = ; i < G[u].size(); i++)

     {

         Edge& e = edges[G[u][i]];

         int v = e.v;

         if(v == fa) continue;

         pre[v] = G[u][i];

         dfs(v, u, d + e.w);

     }

 }

 int main()

 {

     while(scanf("%d%d%d", &n, &s, &k) == )

     {

         edges.clear();

         int tot = ;

         for(int i = ; i <= n; i++) G[i].clear();

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

         {

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

             tot += w;

             AddEdge(u, v, w);

         }

         tot <<= ;

         int ans = ;

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

         {

             len = , id = s;

             pre[s] = -;

             dfs(s, , );

             if(id == s) continue;

             ans += len;

             for(int u = id; u != s; u = edges[pre[u]].u)

             {

                 int& w = edges[pre[u]].w;

                 if(w > ) w = -w;

             }

         }

         printf("%d\n", tot - ans);

     }

     return ;

 }

代码君

巴特西

HDU 4003 Find Metal Mineral

最新文章

热门文章