思路:dp[i][0]表示i是服务器;dp[i][1]表示i不是服务器,但它的父节点是服务器;dp[i][2]表示i和他的父亲都不是服务器。
转移方程:
d[u][0] += min(d[v][0], d[v][1]); d[u][1] += d[v][2]; for(int i = 0; i < n; ++i) { int v= son[u][i]; if(v == pre) continue; d[u][2] = min(d[u][2], d[u][1] - d[v][2] + d[v][0]); }
AC代码:
#include<cstdio> #include<algorithm> #include<cstring> #include<utility> #include<string> #include<iostream> #include<map> #include<set> #include<vector> #include<queue> #include<stack> using namespace std; #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> const int maxn = 10000 + 5; vector<int>son[maxn]; int d[maxn][3]; void dfs(int u, int pre) { d[u][0] = 1; d[u][1] = 0; int n = son[u].size(); for(int i = 0; i < n; ++i) { int v = son[u][i]; if(v == pre) continue; dfs(v, u); d[u][0] += min(d[v][0], d[v][1]); d[u][1] += d[v][2]; if(d[u][0] > inf) d[u][0] = inf; if(d[u][1] > inf) d[u][1] = inf; } d[u][2] = inf; for(int i = 0; i < n; ++i) { int v= son[u][i]; if(v == pre) continue; d[u][2] = min(d[u][2], d[u][1] - d[v][2] + d[v][0]); } } int main() { int END, n; while(scanf("%d", &n) == 1 && n != -1) { for(int i = 0; i <= n; ++i) son[i].clear(); int x, y; for(int i = 1; i < n; ++i) { scanf("%d%d", &x, &y); son[x-1].push_back(y-1); son[y-1].push_back(x-1); } dfs(0, -1); printf("%d\n", min(d[0][0], d[0][2])); scanf("%d", &END); if(END == -1) break; } return 0; }
如有不当之处欢迎指出!