poj 3345 Bribing FIPA (树形背包dp | 输入坑)

题目链接: poj-3345 hdu-2415

题意

有n个国家，你要获取m个国家的支持，获取第i个国家的支持就要给cost[i]的价钱
其中有一些国家是老大和小弟的关系，也就是说，如果你获得了某个老大国家的支持，
那么这个国家的所有小弟(包括小弟的小弟...递归下去)都会无偿免费支持你。
问最少的花费可以得到m个国家的支持

思路

这题还是比较好想的树形dp, 不过输入有些麻烦， 一开始以为每组样例结束都是'#'，结果一直
RE,后来发现最后一组才是 '#'...
国家由于是直接给名字的，所以我用map<string, int>来映射保存编号。

老大和小弟的关系， 其实就是组成了一棵棵的树，那么所有国家的关系就是一个森林。
为了方便进行树形dp， 在增加一个“超级根节点”，森林里所有树的根节点是“超级根节点”的儿子。

那么，用f(i, j)表示子树i, 获取j个国家支持的最少花费

对于子树i，所有节点i的儿子节点都是一组物品，
对于某个儿子，可以选择让他支持1,2..,j个， 那么就是对所有儿子进行分组背包了。。

用tot[v]表示子树v的节点个数
状态转移为：
f[u][i] = min{ f[u][i], f[u][i-j] + f[v][j] | 1<=j<=tot[v] && j<=i && v是u的儿子 };

代码

<script src="https://code.csdn.net/snippets/703.js" type="text/javascript"></script>