P3523 [POI 2011] DYN-Dynamite 题解

管理大大，求过。

题目概括（思路）：

• 这题用二分 + 贪心 + dfs。

• 问题转换：是否能用不超过 $m$ 个点火器，使得所有炸药到最近点火器的距离都不超过 $t$。

具体实现：

初始化：

• $f_u$：子树中未被覆盖炸药到 $u$ 的最大距离，初始值为 $10^9$。

• $gfs_u$：子树中已有点火点到 $u$ 的最小距离；初始值为 $10^9$。

子树合并：

合并规则：

• 如果 $f_v$ 合法（合法区域为：$f_v > -10^9$），就这样：

f[u] = max(f[u], f[v] + 1)

• 如果 $gfs_v$ 合法（合法区域为：$f_v < 10^9$），就这样：

gfs[u] = min(gfs[u], gfs[v] + 1)

贪心 1：

• 如果 $f_u$ 与 $gfs_u$ 都有效，并且 $f_u + gfs_u \le t$，$f_u$ 设为 $-10^9$。

贪心 2：

• 如果 $f_u = t$，说明子树中有一个未覆盖炸药距离 $u$ 恰好为 $t$，所以要在 $u$ 放点火点。

check 函数：

注意：$sum$ 一定一定一定要清零（重要的事情说 $3$ 遍）

• 从根开始 dfs。如果 $f_1 > -10^9$，就：

sum++

• 然后最后就二分，很基础，就不过多赘述了。

AC 代码：

/*
思路：贪心+dfs+二分
问题转换：是否能用不超过m个点火器，使得所有炸药到最近点火器的距离都不超过t
dfs:
f[u] = max(f[u], f[v] + 1);
g[u] = min(g[u], g[v] + 1);
贪心
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;
vector <int> g[MAXN];
int a[MAXN], f[MAXN], gfs[MAXN], sum, n, m;// gfs为子树中最近距离
void dfs (int u, int x, int y) {
    f[u] = -1e9;
    gfs[u] = 1e9;
    if (a[u]) {
        f[u] = 0;
    }
    for (int v : g[u]) {
        if (v == x) {
            continue;
        }
        dfs(v, u, y);
        f[u] = max(f[u], f[v] + 1);
        gfs[u] = min(gfs[u], gfs[v] + 1);
    }
    if (f[u] + gfs[u] <= y) {
        f[u] = -1e9;
    }
    if (f[u] == y) {
        sum++;
        f[u] = -1e9;
        gfs[u] = 0;
    }
}
bool check (int x) {
    sum = 0;
    dfs(1, 0, x);
    if (f[1] >= 0) {
        sum++;
    }
    return sum <= m;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int l = 0, r = n, ans = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

E71 树形DP+二分 P3523 POI2011 DYN-Dynamite

// 树形DP+二分 O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int read(){
  int x=0,f=1;char c=getchar();
  while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
  return x*f;
}

const int N=300005;
int idx,head[N],to[N<<1],ne[N<<1];
void add(int x,int y){
  to[++idx]=y;ne[idx]=head[x];head[x]=idx;
}
int n,m,mid,tot,b[N];
int f[N],g[N];

void dfs(int u,int fa){
  f[u]=-1e9;g[u]=1e9;
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==fa) continue;
    dfs(v,u);
    f[u]=max(f[u],f[v]+1);
    g[u]=min(g[u],g[v]+1);
  }
  if(f[u]+g[u]<=mid) f[u]=-1e9;
  if(g[u]>mid&&b[u]) f[u]=max(f[u],0);
  if(f[u]==mid) f[u]=-1e9,g[u]=0,++tot;
}
int check(){
  tot=0;
  dfs(1,0);
  if(f[1]>=0) ++tot;
  return tot<=m;
}
int main(){
  n=read(),m=read();
  for(int i=1;i<=n;++i)b[i]=read();
  for(int i=1;i<n;++i){
    int x=read(),y=read();
    add(x,y);add(y,x);
  }
  int l=-1,r=n;
  while(l+1<r){
    mid=l+r>>1;
    check()?r=mid:l=mid;
  }
  printf("%d\n",r);
}