问题描述

题目背景

在T市有很多个酒店，这些酒店对于不同种类的食材有不同的需求情况，莱莱公司负责每天给这些酒店运输食材。
由于酒店众多，如何规划运输路线成为了一个非常重要的问题。你作为莱莱公司的顾问，请帮他们解决这个棘手的问题。

题目描述

T市有 $N$ 个酒店，这些酒店由 $N - 1$ 条双向道路连接，所有酒店和道路构成一颗树。不同的道路可能有不同的长度，运输车通过该道路所需要的时间受道路的长度影响。
在T市，一共有 $K$ 种主流食材。莱莱公司有 $K$ 辆车，每辆车负责一种食材的配送，不存在多辆车配送相同的食材。
由于不同酒店的特点不同，因此不同酒店对食材的需求情况也不同，比如可能 $1$ 号酒店只需要第 $1, 5$ 种食材， $2$ 号酒店需要全部的 $K$ 种食材。
莱莱公司每天给这些公司运输食材。对于运输第 $i$ 种食材的车辆，这辆车可以从任意酒店出发，然后将食材运输到所有需要第 $i$ 种食材的酒店。假设运输过程中食材的装卸不花时间，运输车足够大使得其能够在出发时就装满全部所需食材，并且食材的重量不影响运输车的速度。
为了提高配送效率，这 $K$ 辆车可以从不同的酒店出发。但是由于T市对于食品安全特别重视，因此每辆车在配送之前需要进行食品安全检查。鉴于进行食品安全检查的人手不足，最多可以设置 $M$ 个检查点。
现在莱莱公司需要你制定一个运输方案：选定不超过 $M$ 个酒店设立食品安全检查点，确定每辆运输车从哪个检查点出发，规划每辆运输车的路线。
假设所有的食材运输车在进行了食品安全检查之后同时出发，请制定一个运输方案，使得所有酒店的等待时间的最大值最小。酒店的等待时间从运输车辆出发时开始计算，到该酒店所有需要的食材都运输完毕截至。如果一个酒店不需要任何食材，那么它的等待时间为 $0$ 。

输入格式

从标准输入读入数据。
输入的第一行包含 $3$ 个正整数 $N, M, K$ $(N \in [1, 100], 1 \leq M \leq K \leq 10)$ ，含义见题目描述。
接下来 $N$ 行，每行包含 $K$ 个整数。每行输入描述对应酒店对每种食材的需求情况， $1$ 表示需要对应的食材， $0$ 表示不需要。
接下来 $N - 1$ 行，每行包含 $3$ 个整数 $u, v, w$ ，表示存在一条通行时间为 $w$ 的双向道路连接 $u$ 号酒店和 $v$ 号酒店。保证输入数据是一颗树，酒店从 $1$ 编号到 $N$ ，保证 $u, v \in [1, N]$ 并且 $w \in [1, 1 0^{6}]$ 。

输出格式

输出到标准输出。
输出一个整数，表示在你的方案中，所有酒店的等待时间的最大值。

样例 1 输入

样例 1 输出

样例 1 解释

截屏2021-03-21 下午3.29.29.png

样例 1 的输入数据如上图。由于限制了最多只能设置 $1$ 个检查点，因此可以设置两辆运输车的路径如下：

截屏2021-03-21 下午3.29.55.png

在 $2$ 号酒店设置检查点，最晚拿到所有食材的酒店为 $5$ 号酒店，等待时间为 $15$ 。

样例 2 输入

样例 2 输出

样例 2 解释

样例 2 的输入数据和样例 1 几乎完全相同，唯一的区别在于样例 2 中允许最多设置 $2$ 个检查点。我们可以设置两辆运输车的路径如下：
截屏2021-03-21 下午3.30.21.png

在 $1$ 号酒店和 $6$ 号酒店设置检查点，最晚拿到所有食材的酒店为 $3$ 号酒店，等待时间为 $9$ 。

数据规模

分数占比	$N$	$M$	$K$	特殊性
$30%$	$[1, 100]$	$= K$	$[1, 10]$	保证输入数据是一条链，且 $u + 1 = v$
$40%$	$[1, 100]$	$= K$	$[1, 10]$
$30%$	$[1, 100]$	$\leq K$	$[1, 10]$

算法分析

扫描统计：30分
树形DP：70分
树形DP+状压DP：100分

对每一种食材 $c$ 枚举运输车的出发节点 $u$ ，通过树形DP计算出：只考虑这一种食材的情况下，运输车从 $u$ 点出发，所有酒店的最长等待时间。
树形DP中，用 $F [u] [0]$ 表示从 $u$ 点出发，运输车到达了子树中的所有需要这种食材的节点之后再返回 $u$ 点的最短距离；用 $F [u] [1]$ 表示从 $u$ 点出发，运输车到达了子树中的所有需要这种食材的节点之后不返回的最短距离。
当 $M = K$ 时，只需考虑为每一种食材配一个最优的出发点即可。
当 $M < K$ 时，需要做一个状压DP。
状压DP中，用 $d p [s t a t e] [i]$ 表示当前状态是 $s t a t e$ （一个 $K$ 位的二进制数，例如：0110，表示已为第 $2, 3$ 种食材选定了出发点），已经设置了 $i$ 个出发点的答案。
用树形DP的答案直接计算 $d p [s t a t e] [1]$ ，然后 $d p [s t a t e] [i], i \in [2, K]$ 的结果根据之前的状态来推算。

AC代码

截屏2021-03-21 下午4.20.18.png

import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int k = scan.nextInt();
        Graph G = new Graph(n, k);
        for (int i = 1; i <= n; ++ i) {
            for (int j = 0; j < k; ++ j) {
                int x = scan.nextInt();
                G.putTag(i, j, x);
            }
        }
        for (int i = 1; i < n; ++ i) {
            int u = scan.nextInt();
            int v = scan.nextInt();
            int w = scan.nextInt();
            G.addEdge(u, v, w);
        }
        G.solveAns();
        System.out.println(G.solveM(m));
        scan.close();
    }
}

class Graph {
    static int INF = Integer.MAX_VALUE >> 2;
    List<List<int[]>> g;
    int[] tag;
    int n, k;
    int[][] ans;

    public Graph(int _n, int _k) {
        k = _k;
        n = _n;
        g = new ArrayList<>();
        tag = new int[n+1];
        for (int i = 0; i <= n; ++ i) g.add(new ArrayList<>());
        ans = new int[n+1][k];
        for (int i = 0; i <= n; ++ i) Arrays.fill(ans[i], INF);
    }

    public void addEdge(int u, int v, int w) {
        g.get(u).add(new int[]{v, w});
        g.get(v).add(new int[]{u, w});
    }

    public void putTag(int u, int pos, int x) {
        tag[u] |= (x << pos);
    }

    private int getTag(int u, int num) {
        return (tag[u] >> num) & 1;
    }

    private int[] dfs(int u, int fa, int faw, int cntTag) {
        int maxProfit = 0;
        int utag = getTag(u, cntTag);
        int sumLen = 0;
        for (int[] edge : g.get(u)) {
            int v = edge[0], w = edge[1];
            if (v == fa) continue;
            int[] x = dfs(v, u, w, cntTag);
            utag |= x[0];
            sumLen += x[1];
            maxProfit = Math.max(maxProfit, x[1]-x[2]);
        }
        if (utag == 0) return new int[]{0, 0, 0};
        return new int[]{1, sumLen+2*faw, sumLen+faw-maxProfit};
    }

    public void solveAns() {
        for (int i = 1; i <= n; ++ i) {
            for (int j = 0; j < k; ++ j) {
                int[] temp = dfs(i, -1, 0, j);
                ans[i][j] = temp[2];
            }
        }
    }

    private int getAns(int u, int state) {
        int ret = 0;
        for (int i = 0; i < k; ++ i) {
            if (((state >> i) & 1) == 1) {
                ret = Math.max(ret, ans[u][i]);
            }
        }
        return ret;
    }

    public int solveM(int m) {
        int[][] dp = new int[1 << k][m+1];
        for (int state = 0; state < (1 << k); ++ state) {
            dp[state][1] = INF;
            for (int i = 1; i <= n; ++ i) {
                dp[state][1] = Math.min(dp[state][1], getAns(i, state));
            }
        }
        for (int i = 2; i <= m; ++ i) {
            for (int state = 0; state < (1 << k); ++ state) {
                dp[state][i] = INF;
                for (int sub = state&(state-1); sub != 0; sub = (sub-1)&state) {
                    dp[state][i] = Math.min(dp[state][i], Math.max(dp[sub][i-1], dp[state^sub][1]));
                }
            }
        }
        int ret = INF;
        for (int i = 1; i <= m; ++ i) {
            ret = Math.min(ret, dp[(1 << k)-1][i]);
        }
        return ret;
    }
}