算法

状压DP+二分

根据题意，我们可以将本题抽象成如下问题：
在n个点中选取至多m个点，每个点送出一种食材，这m个点能满足所有的K种需求，且配送的最大时间最短。

那么我们可以二分答案，因为答案所求为等待的最大时间，我们需要预处理所有酒店的配送时间：

令d[i][j] 表示从酒店i出发，走完所有需要食材j的酒店耗费的最短时间(即最后停在距离i最远的酒店)

那么对所有d[i][j] <= mid的n个酒店来说，每个酒店在此限制下都会有一个配送状态，因为k最大为10
考虑状态压缩，用state[i] 表示上面限制下酒店i对k种食材的配送状态，1为可以配送，0为不能配送
对于n个state状态，我们现在从中选最多m个，使得覆盖所有k个需求，状态DP:

dp[i] ： 表示所有满足状态i表示需求的情况中的最少酒店数目
状态转移：枚举所有酒店j dp[i | state[j]] = min(dp[i | state[j]], dp[i] + 1);

如何预处理d数组
对d[i][j] 来说
考虑回到原点，那么记A为从i走到所有需要j食材酒单的两倍路径和
如果不回到原点，那么就是找到离i最远的需要食材j的酒店，记此距离为a
那么d[i][j] = A - a; 两次dfs即可

时间复杂度

状压： O(2^k * N)
预处理： O(N * N * K)
时间复杂度： O(2^k * N + N * N *K)

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 2*N, C = 1<<11;

typedef pair<int,int> PII;
int h[N],e[M],w[M],ne[M],idx;
int n,m,k;
int state[C],dp[C];  // state[i] 表示i号酒店对K种需求的满足情况
                    // dp[i] 表示所有满足状态i表示需求的情况中的最少酒店数目
bool fd[N][11];  // fd[i][j] : i号酒店是否需要食材j
int d[N][11];   // d[i][j] 表示从i号酒店出发，走完所有需要食材j的酒店的最短时间(最后停在距离i最远的地方)


void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

// 双倍距离
int dfs1(int u,int fa,int food){
    int res = 0;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j == fa) continue;
        int t = dfs1(j,u,food);
        if(t) {
            res += t + w[i] * 2;
        }else{
            if(fd[j][food]) res += w[i] * 2;
        }
    }
    return res;
}

// 找距离i号酒店最远的点
int dfs2(int u,int fa,int food){
    int res = 0;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j == fa) continue;
        int t = dfs2(j,u,food);
        if(t || fd[j][food]){
            res = max(res,t + w[i]);
        }
    }
    return res;
}

// 同时求
// PII dfs3(int u,int fa,int food){
//     PII  res(0,-1);
//     if(fd[u][food]) res.second = 0;
//     for(int i = h[u]; ~i; i = ne[i]){
//         int j = e[i];
//         if(j == fa) continue;
//         PII t = dfs3(j,u,food);
//         if(t.second != -1){
//             res.first += t.first + w[i] * 2;
//             res.second = max(res.second, t.second+w[i]);
//         }
//     }
//     return res;
// }

bool check(int x){
    memset(state,0,sizeof state);
    for(int i = 1; i<=n; i++){
        for(int j = 0; j<k; j++){
            if(d[i][j] <= x) state[i] |= 1 << j;
        }
    }
    memset(dp,0x3f,sizeof dp);
    dp[0] = 0;

    for(int i = 0; i<1<<k; i++){
        for(int j = 1; j<=n; j++){
            dp[i | state[j]] = min(dp[i | state[j]], dp[i] + 1);
        }
    }
    return dp[(1<<k)-1] <= m;  // 检查点数量
}
int main()
{
    cin>>n>>m>>k;

    for(int i = 1; i<=n; i++){
        for(int j = 0; j<k; j++){
            cin>>fd[i][j];
        }
    }

    memset(h,-1,sizeof h);
    for(int i = 1; i<n; i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    // 预处理d[i][j]
    for(int i = 1; i<=n; i++){
        for(int j = 0; j<k; j++){
            d[i][j] = dfs1(i,-1,j) - dfs2(i,-1,j);
        }
    }

    int l = 0, r = 1e9;
    while(l<r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout<<l<<endl;
    return 0;
}