食材运输
问题描述
在$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$行，每行包含$K$个整数。每行输入描述对应酒店对每种食材的需求情况，$1$表示需要对应的食材，$0$表示不需要。
接下来$N−1$行，每行包含$3$个整数$u,v,w$，表示存在一条通行时间为$w$的双向道路连接$u$号酒店和$v$号酒店。
保证输入数据是一颗树，酒店从$1$编号到$N$。
输出格式
输出一个整数，表示在你的方案中，所有酒店的等待时间的最大值。
数据范围
对于所有数据，满足
$1\leq N\leq 10^2$,
$1\leq M\leq K\leq 10$,
$1\leq u,v\leq N$,
$1\leq w\leq 10^6$。
具体数据规模如下：
输入样例1：
1
2
3
4
5
6
7
8
9
10
11
12
| 6 1 2
1 0
0 0
1 0
0 1
0 1
0 1
1 2 7
2 3 2
2 4 4
4 5 5
4 6 3
|
输出样例1：
样例1解释
样例$1$的输入数据如上图。
由于限制了最多只能设置$1$个检查点，因此可以设置两辆运输车的路径如下：
输入样例2：
1
2
3
4
5
6
7
8
9
10
11
12
| 6 2 2
1 0
0 0
1 0
0 1
0 1
0 1
1 2 7
2 3 2
2 4 4
4 5 5
4 6 3
|
输出样例2：
样例2解释
样例$2$的输入数据和样例$1$几乎完全相同，唯一的区别在于样例$2$中允许最多设置$2$个检查点。
我们可以设置两辆运输车的路径如下：
在$1$号酒店和$6$号酒店设置检查点，最晚拿到所有食材的酒店为$5$号酒店，等待时间为$15$。
解题思路
给定$n$个顶点的树，从中选取不超过$m$个点，在限定时间内实现区间覆盖
题目要求求解最长时间的最小值，这个值具有二段性：如果时间过小，则无论如何选取$m$个点，都不能实现$k$种食材完全运输完毕；如果时间过大，就有冗余。综上，对时间进行二分。
暂且不考虑至多选取$m$个点的限制，那么问题可以视为一个区间重复覆盖问题：对于任意一个点$i$，计算其运输$j$种物品的最长时间$d[i][j]$，$state[i]$是一个二进制数，表示在时限从i点出发所能运送完的食材种类状态，能运送完，则相应数位为$1$，否则为$0$；
根据$2$知，需要$DFS$预处理$d[i][j]$;
二分的$check$函数：状压$DP$，$f[j]$表示达到状态$j$所需选择的最少节点数量；那么如果f[(1 << k) - 1] <= m，$check$就返回真值即可。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110,M = 15,inf = 0x3f3f3f3f;
typedef pair<int, int> PII;
#define x first
#define y second
int n,m,k;
int food[N][M];
int d[N][M];
int f[1 << M];
int state[N];
int h[N],idx;
struct edge{
int to,ne,w;
}e[N * 2];
void init(){
for(int i = 1; i <= n; ++ i) h[i] = -1;
}
void add(int x,int y,int w){
e[idx].to = y,e[idx].w = w,e[idx].ne = h[x],h[x] = idx ++;
}
PII dfs(int u,int fa,int k) {
PII res = {0,-1};
if(food[u][k]) res.y = 0;
for(int i = h[u]; ~i; i = e[i].ne) {
int j = e[i].to,w = e[i].w;
if(j == fa) continue;
PII t = dfs(j,u,k);
if(t.y != -1) {
res.x += t.x + w * 2;
res.y = max(res.y,w + t.y);
}
}
return res;
}
bool check(int mid) {
for(int i = 1; i <= n; ++ i) state[i] = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j < k; ++ j)
if(d[i][j] <= mid)
state[i] |= 1 << j;
for(int i = 0; i < 1 << k; ++ i) f[i] = inf;
f[0] = 0;
for(int i = 0; i < 1 << k; ++ i)
for(int j = 1; j <= n; ++ j)
f[i | state[j]] = min(f[i | state[j]],f[i] + 1);
return f[(1 << k) - 1] <= m;
}
int main() {
cin.tie(nullptr);cout.tie(nullptr);ios::sync_with_stdio(false);
cin >> n >> m >> k;
for(int i = 1; i <= n; ++ i)
for(int j = 0; j < k; ++ j)
cin >> food[i][j];
init();
int a,b,w;
for(int i = 1; i <= n - 1;++ i) {
cin >> a >> b >> w;
add(a,b,w);add(b,a,w);
}
for(int i = 1; i <= n; ++ i)
for(int j = 0; j < k; ++ j) {
PII t = dfs(i,-1,j);
if(~t.y) d[i][j] = t.x - t.y;
}
int l = 0,r = inf;
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}
|
