寒假集训——FindMetalMineral

Z时代
2024-01-10
分类：综合

coding

题目链接

题意：给出一颗生成树，1<=N<=10000，在某一个节点有k个机器人（k<=10）,然后机器人从这里开始走,要求遍历完节点,随便停到什么地方.求最少的路程总和.

题解: 树形dp,关键是dp[u][i],i的定义,因为机器人可能从子树再跑回来,然后为了避免重复讨论,应该定义为:在u为根的子树上停了几个机器人.这样定义肯定不会重复,重点就是之后的横着怎么dp过去.考虑最后一个,枚举它:如果是0,那么一定是只有一个机器人进来然后绕了一圈走了,可以反证.如果是1,一定是1个,反证可以,之后i个就是i..... 然后就能这样dp过去.定位也很关键,对于每一个子树的选择是:必须只能选一个的背包.

重点:树形dp中i的正确不重复定义,有效避免枚举,然后在这基础上正确推出dp方程.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctype.h>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#define CLR(a) memset(a, 0, sizeof(a))
#define REP(i, a, b) for(int i = a;i < b;i++)
#define REP_D(i, a, b) for(int i = a;i <= b;i++)
typedef long long ll;
using namespace std;
const int maxn = 10000 + 100;
int n, s, k, dp[maxn][20], vis[maxn];
struct info
{
    int to, w;
};
vector<info> G[maxn];
void dfs(int u)
{
    vis[u] = 1;//树形dp
    for(int i = 0;i <= k;i++)//初始化,现在什么都没有,如果是叶子节点也是这样
    {
        dp[u][i] = 0;
    }
    //dp[u][0] = 0;
    int tt = G[u].size();
    //printf("---- %d\n", tt);
    for(int m = 0;m < tt;m++)
    {
        int to = G[u][m].to;
        int w = G[u][m].w;
        if(!vis[to])//开始子树
        {
            dfs(to);//先弄掉子树
            for(int i = k; i >= 0; i--)//倒着扫
            {
                dp[u][i] += dp[to][0] + 2*w;//重点,因为一定要"选"这么多情况的一种,先随便用0来填充.
                for(int j = 1; j <= i; j++)
                {
                    dp[u][i] = min(dp[u][i], dp[u][i - j] + j*w + dp[to][j]);//取小
                }
            }
        }
    }
//    if(flag == 0)
//    {
//        for(int i = 0;i <= k;i++)
//        {
//            dp[u][i] = 0;
//        }
//    }
}
void solve()
{
    CLR(dp);
    CLR(vis);
    dfs(s);
    printf("%d\n", dp[s][k]);
}
int main()
{
 //   freopen("13Min.txt", "r", stdin);
    //freopen("1out.txt", "w", stdout);
    while(scanf("%d%d%d", &n, &s, &k) != EOF)
    {
        REP_D(i, 1, n)
        {
            G[i].clear();
        }
        REP_D(i, 1, n - 1)
        {
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);
            info tmp;
            tmp.to = b;
            tmp.w = w;
            G[a].push_back(tmp);
            tmp.to = a;
            G[b].push_back(tmp);
        }
        solve();
    }
    return 0;}