202012-4 食材运输

思路：

这道题还是很难的，不过一步步分析下来就感觉还可以。首先求最大值最小问题，肯定就是使用二分法，在所有可能的答案范围内不断二分，直到找到第一个满足要求的时间，那就是最小值。然后，对于某个酒店，它运输某个食材的最短时间是可以求出来的，用dfs。这里是用了它到所有需要食材的酒店的路径和乘以2，再出发点到某个需要食材的酒店的最长路径得到的。这里的DFS用法很巧妙，它使用最长路径是否存在表示它子树中是否存在需要食材的酒店，因为如果存在那么最长路径必定不为-1，至少为0。最后对于二分的每个长度，首先利用之前求到的数组d[i][j]，看他是否小于等于mid，如果是那么这个酒店就可以运输第j种食材，把它的对应状态标记为1.最后进行状压DP，每个状态表示它当前送达的食材所需的最小起点数，由每个状态或每个酒店能到达的点得到它能够去的下一个状态，求最小值即可。

反思：

慢慢分析就还行，可惜没有那么多时间
代码：

#include 
#include 
#include 
#include 
using namespace std;
#define x first
#define y second
typedef pair PII;
const int N = 105;
const int M = 2 * N;
const int K = 10;
const int S = 1 << K;
int h[N], e[M], w[M], ne[M], idx;
int d[N][K];//表示每个酒店送某种食材的最短距离
int need[N][K];//表示每个酒店是否需要某种食材 
int f[S];//表示每一种食材送达状态所需要的最小起点数 
int state[N];//表示每一个酒店对于mid可以送的食材标识 
int n,m,k;
void add(int a, int b,int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
PII dfs(int u, int fa, int v){
	PII res = {0, -1};
	if(need[u][v])res.y = 0;
	for(int i = h[u];i != -1;i = ne[i]){
		int j = e[i];
		if(j == fa)continue;
		auto t = dfs(j, u, v);
		if(t.y != -1){
			res.x += t.x + 2 * w[i];
			res.y = max(t.y + w[i], res.y);
 		}
	}
	return res;
}
bool check(int mid){
	memset(state, 0, sizeof(state));
	for(int i = 1;i<=n;i++){
		for(int j = 0;j>n>>m>>k;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j>need[i][j];
		}
	}
	for(int i = 1;i<=n - 1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u, v, w);
		add(v, u, w);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j> 1;
		if(check(mid)){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	cout<