题解 UVA1218 【完美的服务 Perfect Service】
chihik
·
·
题解
一道很不错的树形dp。
令 dp[u][f] 为以u为根的子树。
$f=1$，表示$u$的父亲为服务器，那么$u$的儿子一定不为服务器。
$f=2$，表示$u$和$u$的父亲均不为服务器，那么$u$的儿子中一定有一个是服务器。
那么转移式为:
$$
dp[u][0]=\sum_{v \in son_u}min(dp[v][0],dp[v][1])
$$
$$
dp[u][1]=\sum_{v \in son_u}dp[v][2]
$$
$$
dp[u][2]=min(dp[v_1][2]+dp[v_2][2]+...+dp[v_k][0]+...+dp[v_s][2])
$$
其中 $s$ 为 $u$ 的子结点个数 ， $k$ 是枚举的为服务器的那个子节点。
这样转移需要$\Theta(n)$ ， 经过观察发现，求和的部分与 $dp[u][1]$ 除了枚举的 $dp[v_k][0]$ 是一致的 ， 于是就可以化简为：
$$
dp[u][2]=min(dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ])
$$
最后注意$\text{dp}$的极大值,用 $inf$ 可能会爆 $int$ , 开成 $n+5$ 即可。
```cpp
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 10000;
int n , u , v , dp[ MAXN + 5 ][ 3 ];
vector< int > Graph[ MAXN + 5 ];
void dfs( int u , int fa ) {
dp[ u ][ 0 ] = 1; dp[ u ][ 1 ] = 0;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs( v , u );
dp[ u ][ 0 ] += min( dp[ v ][ 0 ] , dp[ v ][ 1 ] );
dp[ u ][ 1 ] += dp[ v ][ 2 ];
dp[ u ][ 2 ] = min( dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ] );
}
}
int main( ) {
while( scanf("%d",&n) ) {
for( int i = 1 ; i <= n ; i ++ ) {
Graph[ i ].clear( );
dp[ i ][ 0 ] = dp[ i ][ 1 ] = dp[ i ][ 2 ] = MAXN;
}
for( int i = 1 ; i <= n - 1 ; i ++ ) {
scanf("%d %d",&u,&v);
Graph[ u ].push_back( v );
Graph[ v ].push_back( u );
}
dfs( 1 , 0 );
printf("%d\n", min( dp[ 1 ][ 0 ] , dp[ 1 ][ 2 ] ) );
scanf("%d",&n);
if( n == -1 ) break;
}
return 0;
}
```