期末大作业
题目1：食材运输
题意
某市一共有\(n\)个酒店编号为\(1\)到\(n\)，酒店之间由\(n - 1\)条无向边连接构成一棵树，并且每条边具有权值（时间），现在有\(k\)种食材对应\(k\)辆车配送，每个酒店所需要的食材种类不同，现在你需要根据每个酒店需要不同食材的情况以及酒店之间的边权来选择\(m\)个酒店，让这\(k\)个车辆只能从这\(m\)个酒店出发，使得完成相应配送时所有酒店等待时间的最大值最小。
数据范围
\(1 \leq n\leq 100, 1 \leq m \leq k \leq 10\)，输入所给的从酒店\(u\)到酒店\(v\)间的时间\(w\)满足\(1 \leq w \leq 10^{6}\).
时间限制与空间限制
时间限制：1.0s
空间限制：512MB
题解
解法一：
只考虑输入数据是一条链的情况，此时同时满足\(m = k\)。我们发现对于完成某种食材的配送的所需时间即为在所有需要这种食材的酒店构成的链上，从链头酒店到达链尾酒店的时间（容易证明这样配送耗费的时间是最小的），不妨记配送第\(i\)种食材的这个时间为\(t_i\)，易知答案即为\(max(t_1, t_2, ..., t_k).\)
时间复杂度：\(O(nk)\) 空间复杂度：\(O(n)\)
期望得分：25
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define x first
#define y second
int n, m, k;
const int N = 110;
typedef pair<int, int> PII;
vector<vector<int> > v(N, vector<int> (12));
vector<vector<int> > g(N, vector<int> (N));
PII a[12];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= k; j ++ )
cin >> v[i][j];
for (int i = 1; i < n; i ++ )
{
int u, v, w;
cin >> u >> v >> w;
g[u][v] = w;
g[v][u] = w;
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= k; j ++ )
{
if (v[i][j] && !a[j].x) a[j].x = i;
if (v[i][j]) a[j].y = i;
}
}
int res = 0;
for (int i = 1; i <= k; i ++ )
{
int t = 0;
if (a[i].x != a[i].y)
{
int n1 = a[i].x, n2 = a[i].y;
for (int j = n1; j < n2; j ++ ) t += g[j][j + 1];
}
res = max(res, t);
}
cout << res << "\n";
return 0;
}