史上最难T4
$\quad$1.圣人y总曾说过,十位数的数据情况,多半是状压
$\quad$2.题目关键字眼,最大值最小,即可确认要用到二分
$\quad$3.从酒店u出发的送v号食材的车,可以通过dfs确定该车的最短行程,且让此车停到最远的一个酒店不用回来
$\quad$4.然后就是一个重复覆盖问题,dacing links或者本题特殊的状态压缩dp都可以
$\quad$5.二分枚举答案,超过mid的酒店就不选取,查看在这种选取情况下能否满足仅开设m个以内的检查点
#include <bits/stdc++.h>
using namespace std;
const int N = 110,M=2*N,K=15;
int need[N][K];
int h[N], e[M], w[M], ne[M], idx;
int dist[N][K];
bool st[N];
int n,m,k;
typedef pair<int, int> PII;
#define x first
#define y second
int f[1<<K],state[N];
void add(int a, int b, int c) // 添加一条边a->b,边权为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;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+w[i]*2;
res.y=max(res.y,t.y+w[i]);
}
}
return res;
}
bool check(int mid){
memset(state,0,sizeof state);
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
if(dist[i][j]<=mid) state[i]|=1<<j;
}
}
memset(f,0x3f,sizeof f);
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()
{
scanf("%d%d%d", &n, &m, &k);
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
scanf("%d",&need[i][j]);
}
}
memset(h, -1, sizeof h);
for(int i=0;i<n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);add(b,a,c);
}
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
auto t=dfs(i,-1,j);
if(t.y!=-1) dist[i][j]=t.x-t.y;
}
}
int l=0,r=1e9;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}