UVA 1218 Perfect Service——dp

UVA 1218 Perfect Service——dp

一开始题目没读好，各种错误定义，所以提醒大家做题之前一定要认真读题。。。。。。

加上读错题浪费的时间，这题一共做了两个小时，一开始我以为这是两遍dfs综合考虑父树子树状态的题目，但进行了一些尝试后我发现只用子树状态就可以完成这道题目

然后是找有用的状态，这个不是很难想，最基本的状态就是一个点是建服务器还是不建服务器，我们用黑点表示建服务器，白点表示不建服务器，考虑题目的限制，一个状态至少要包含树中的两层信息，基于这一点我们最终找到了（根节点为白点，子节点全为白点）、（根节点为白点，子节点有一个黑点，其余全为白点）、（根节点为黑点，子节点任意）这三个有效状态，用x【i】，y【i】，z【i】表示

接着是状态转移，其实说白了我就是靠着状态转移找的有效状态，这个也不是很难想(下面的i为父节点，j为i的子节点)，x【i】=sum{y【j】}，y【i】=min{x【i】-y【j】+z【j】}，z【j】=sum{min{x【j】，z【j】}}；

最终结果就是min{y【1】，z【1】}（默认1为根节点）

最后是边界，这个是我做这个题遇到的难点，因为叶子节点的x【i】，y【i】似乎不好确定，其实多画几个图就会发现，叶节点的x【i】=0，y【i】=INF，这个INF表示这个状态是错误的，也就是说叶节点有状态x没有状态y（别问我状态z，z太好想了。。。），但是回溯时x【i】的值为y【j】的和，如果y【j】为INF，那么x【i】不就爆炸了吗？首先我们把INF设置为1w多一点的数，保证一次求和不会溢出，然后回溯时发现由于有y【i】=min（y【i】，x【i】-y【j】+z【j】），所以y【i】的值不会超过INF，继续回溯下去可知x的值不会很大，然后就做完了

#include #include #include #include #include using namespace std;const int maxn = 1e4 + 10;const int INF = 1e4 + 10;int n;vector G[maxn];int x[maxn], y[maxn], z[maxn];void dfs(int u, int p) { x[u] = 0, y[u] = INF, z[u] = 1; if (G[u].size() == 0) return; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (v == p) continue; dfs(v, u); x[u] += y[v]; z[u] += min(x[v], z[v]); } for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (v == p) continue; y[u] = min(y[u], x[u]-y[v]+z[v]); }}int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) G[i].clear(); int u, v; for (int i = 1; i <= n-1; i++) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, -1); printf("%d\n", min(y[1], z[1])); int t; scanf("%d", &t); if (t == -1) break; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。