题解：CF70E Information Reform
Lovya
·
·
题解
:::info[简要题意]{open}
给定一棵 n 个点的树，边长为 1。
选择若干个点，在点上建立 center，每个 center 的建立需要 k 元的花费。
对于每个点 i，如果点 i 上没有建立 center，则 l 表示点 i 与最近的 center 之间的距离，点 i 需要 d[l] 元的花费。
求一种建立 center 的方案，使得总花费最小。
:::
$F[v,s]$ 表示保证内部有一个 center 到点 $v$ 的距离 $\le s$ 时，花费的最小值。
$G[v,s]$ 表示保证外部有一个 center 到点 $v$ 的距离 $= s$ 时，花费的最小值。
（1）初始状态，$s=0$ 时，选择 $v$ 作为 center，花费 $k$ 元。且此时对于 $v$ 的子节点 $c$ 而言，到外部最近的 center 距离为 $1$，即 $G[c,1]$。
$$
F[v,0]=k+\sum_{c \in son(v)} G[c,1]
$$
（2）转移 $G[v,s]$：外部有一个 center 到点 $v$ 的距离 $= s$ 时，分情况讨论：
1. 内部有一个 center 到点 $v$ 的距离 $\le s$ 时，可以直接从内部的 center 转移，即 $F[v,s]$。
2. 从外部到点 $v$ 距离为 $s$ 的 center 转移。此时点 $v$ 需要 $d[s]$ 的花费，且对于 $v$ 的子节点 $c$ 而言，到外部的 center 距离为 $s+1$，即 $G[c,s+1]$。
$$
G[v,s]=\min
\begin{cases}
F[v,s]\\
d[s]+\sum_{c \in son(v)} G[c,s+1]
\end{cases}
$$
（3）转移 $F[v,s]$：内部存在一个 center 到点 $v$ 的距离 $\le s$ 时，分情况讨论：
1. 当内部存在一个 center 到点 $v$ 的距离 $\le s - 1$ 时，同时也就满足内部存在一个 center 到点 $v$ 的距离 $\le s$。因此可以从 $F[v,s-1]$ 转移。
2. 当内部不存在一个 center 到点 $v$ 的距离 $\le s - 1$ 时，则此时必然选择一个到点 $v$ 的距离 $= s$ 的 center 作为内部最近的 center，需要 $d[s]$ 的花费。同时，对于除了该到点 $v$ 的距离 $= s$ 的 center 的祖先 $c$ 外，其余点 $v$ 的子节点 $u$ 到该 center 的距离为 $s+1$，即从 $G[u,s+1]$ 转移。
$$
F[v,s]=\min
\begin{cases}
F[v,s-1]\\
\min_{c \in son(v)} d[s]+F[c,s-1]+\sum_{u \in son(v),u \not = c} G[u,s+1]
\end{cases}
$$
注意到，虽然 $F[c,s-1]$ 中选取的 center 未必到点 $v$ 的距离 $= s$，但 $< s$ 的情况已经被 $F[v,s-1]$ 的转移包含在内，两者取 $\min$，不影响结果。
最坏情况下，转移 $F[v,s]$ 的时间复杂度是 $\Omicron(n)$ 的。状态数最坏情况下是 $\Omicron(n^2)$ 的。$1 \le n \le 180$，可以通过。
答案即为 $\min_s F[root,s]$。
这道题还有一个问题，是需要输出使花费最小时，每个点 $i$ 所依靠的 center。
通过 BFS 计算任意两点 $i,j$ 之间的距离 $dist_{i,j}$。
通过回溯最小花费 $F[root,s]$ 的计算过程，确定所选取的 center，并记录每个点 $v$ 到其转移过程设计的最近 center 的距离 $Min_v$。
对于每个非 center 的点 $i$，依次枚举 center 点 $j$，若 $Min_i=dist_{i,j}$，则可以认为点 $j$ 是点 $i$ 所依靠的 center。
具体细节参见代码。
:::info[code]{open}
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
#include<utility>
#include<cmath>
using namespace std;
int n,m,k,x,y,w_cnt,d[185],w_head[185],f[185][185],g[185][185],w_id[185],w_min[185],w_dist[185][185];
bool w_vis[185];
pair<int,int> w_now;
queue<pair<int,int> > q;
struct node{
int w_next,w_to;
}w_edge[365];
void w_add(int u,int v)
{
w_edge[++m]={w_head[u],v};
w_head[u]=m;
}
void w_dfs(int v,int w_fa)
{
f[v][0]=k;
for(int i=w_head[v];i;i=w_edge[i].w_next)
{
if(w_edge[i].w_to==w_fa)
continue;
w_dfs(w_edge[i].w_to,v);
f[v][0]+=g[w_edge[i].w_to][1];
}
// printf("f[%d][0]=%d\n",v,f[v][0]);
int w_temp=0;
for(int s=1;s<n;s++)
{
f[v][s]=f[v][s-1];
for(int i=w_head[v];i;i=w_edge[i].w_next)
{
if(w_edge[i].w_to==w_fa)
continue;
w_temp=d[s]+f[w_edge[i].w_to][s-1];
for(int j=w_head[v];j;j=w_edge[j].w_next)
{
if(w_edge[j].w_to==w_fa||w_edge[j].w_to==w_edge[i].w_to)
continue;
if(g[w_edge[j].w_to][s+1]==1e9)
w_temp=1e9;
else
w_temp+=g[w_edge[j].w_to][s+1];
}
f[v][s]=min(f[v][s],w_temp);
}
g[v][s]=f[v][s];
w_temp=0;
for(int i=w_head[v];i;i=w_edge[i].w_next)
{
if(w_edge[i].w_to==w_fa)
continue;
if(g[w_edge[i].w_to][s+1]==1e9)
w_temp=1e9;
else
w_temp+=g[w_edge[i].w_to][s+1];
}
g[v][s]=min(g[v][s],w_temp+d[s]);
// printf("f[%d][%d]=%d,g[%d][%d]=%d\n",v,s,f[v][s],v,s,g[v][s]);
}
f[v][n]=g[v][n]=1e9;
}
void w_solve(int v,int s,int w_fa,int w_pos)
{
// printf("solve(%d,%d,%d,%d)\n",v,s,w_fa,w_pos);
int w_temp=0;
if(w_pos==0)
{
if(!s)
{
w_id[v]=v;
w_min[v]=0;
for(int i=w_head[v];i;i=w_edge[i].w_next)
{
if(w_edge[i].w_to==w_fa)
continue;
w_solve(w_edge[i].w_to,1,v,1);
}
return;
}
if(f[v][s]==f[v][s-1])
{
w_solve(v,s-1,w_fa,0);
return;
}
w_temp=0;
for(int i=w_head[v];i;i=w_edge[i].w_next)
{
if(w_edge[i].w_to==w_fa)
continue;
w_temp=d[s]+f[w_edge[i].w_to][s-1];
for(int j=w_head[v];j;j=w_edge[j].w_next)
{
if(w_edge[j].w_to==w_fa||w_edge[j].w_to==w_edge[i].w_to)
continue;
if(g[w_edge[j].w_to][s+1]==1e9)
w_temp=1e9;
else
w_temp+=g[w_edge[j].w_to][s+1];
}
if(w_temp==f[v][s])
{
w_min[v]=s;
w_solve(w_edge[i].w_to,s-1,v,0);
for(int j=w_head[v];j;j=w_edge[j].w_next)
{
if(w_edge[j].w_to==w_fa||w_edge[j].w_to==w_edge[i].w_to)
continue;
w_solve(w_edge[j].w_to,s+1,v,1);
}
return;
}
}
}
else
{
if(g[v][s]==f[v][s])
{
w_solve(v,s,w_fa,0);
return;
}
w_min[v]=s;
for(int i=w_head[v];i;i=w_edge[i].w_next)
{
if(w_edge[i].w_to==w_fa)
continue;
w_solve(w_edge[i].w_to,s+1,v,1);
}
}
}
void w_bfs(int v)
{
while(!q.empty())
q.pop();
q.push({v,0});
while(!q.empty())
{
w_now=q.front();
q.pop();
if(w_dist[v][w_now.first])
continue;
w_dist[v][w_now.first]=w_now.second;
for(int i=w_head[w_now.first];i;i=w_edge[i].w_next)
q.push({w_edge[i].w_to,w_now.second+1});
}
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<n;i++)
scanf("%d",&d[i]);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
w_add(x,y);
w_add(y,x);
}
for(int i=1;i<=n;i++)
w_bfs(i);
w_dfs(1,0);
w_cnt=0;
for(int i=1;i<=n;i++)
{
if(f[1][i]<f[1][w_cnt])
w_cnt=i;
}
printf("%d\n",f[1][w_cnt]);
w_solve(1,w_cnt,0,0);
for(int i=1;i<=n;i++)
{
if(w_id[i]==i)
continue;
for(int j=1;j<=n;j++)
{
if(w_id[j]!=j)
continue;
if(w_dist[i][j]==w_min[i])
{
w_id[i]=j;
break;
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",w_id[i]);
return 0;
}
```
:::