Poj 3345 Bribing FIPA (DP_树形DP(背包))
题目链接：http://poj.org/problem?id=3345

题目大意：xx大佬要竞选xx职位，现一共有n个国家，获得xx职位至少需要m个国家的支持，某个国家下面会有若干个附属国家，这个代表获得这个国家的支持就可以获得一群国家的支持。想要获得这个国家的支持，就必须拿钻石去贿赂，好厚黑。问获得xx职位最少需要多少钻石。

解题思路：树形DP+分组背包，状态转移方程很好想，但是输入很难处理。我最早的方法是用getchar一个一个输入，这样一直判断肯定最妥，但是要写很长，后来输入n和m用了sscanf，输入各个国家的情况用了scanf，然后代码瞬间变短。输入虽恶心，但注意下就不会错。由于要至少m个国家的支持，那么可以以国家数作为费用，付出的钻石作为价值，最后求费用大等于m时的最小价值。

设dp[i][j]表示以i节点跟根节点的书中选择j个国家的最小价值。

状态转移方程:dp[i][j] = min(dp[i][j],dp[i->son][k]+dp[i->son][j-k]);

dp[i][num[son]] = cost[son];//num[son]表示包括i节点在内的最少费用

这题犯了一个致命错误，在输入的时候i从1到n逐个输入，但是应该根据当前国家在map的位置来定下标，即是cost[map[a]] = k,而不是cost[j] = k，

就因为这个小错误调试调了一下午，蛋疼。对于自己写的算法，要有足够的信心，要知道很多时候都只是编程时的小问题导致一直Wa.另外，这题用vector建树似乎速度更快，静态链表为63ms，vector的可以达到16ms。

测试数据：
10 4
e 15 a b c d
a 10
b 10
c 10
d 10
f 1
g 3
h 3
i 40
j 16 f g h i
10 1
a 10
b 10
c 10
d 10
e 15 a b c d
f 0
g 3
h 3
i 40
j 16 f g h i
3 2
Aland 10
Boland 20 Aland
Coland 15
3 0
a 10
b 10
c 20
3 1
a 10
b 30
c 20

#

代码：#include <stdio.h>#include <string.h>#include <map>#include <string>using namespace std;#define MAX 300#define INF 1000000000#define min(a,b) (a)<(b)?(a):(b)struct node { int v; node *next;}*head[MAX],tree[MAX];map<string,int> mmap;int tot,ptr,n,m,vis[MAX]; //vis表示是不是根节点int num[MAX],cost[MAX]; //num[i]表示包括自己和子节点的个数int ans,dp[MAX][MAX]; //dp[i][j]表示节点i收买j个国家的最小花费void Initial() { //初始化 mmap.clear(); ptr = tot = 1,ans = INF; for (int i = 0; i < MAX; ++i) { for (int j = 0; j < MAX; ++j) dp[i][j] = INF; head[i] = NULL; num[i] = vis[i] = cost[i] = 0; }}void AddEdge(int x,int y){ //添加节点 tree[ptr].v = y; tree[ptr].next = head[x],head[x] = &tree[ptr++];}void Tree_DP(int son) { int i,j,k; node *p = head[son]; dp[son][0] = 0,p = head[son]; while (p != NULL) { Tree_DP(p->v);num[son] += num[p->v]; for (j = num[son]; j >= 0; --j) for (k = 0; k <= num[p->v] && k <= j; ++k) dp[son][j] = min(dp[son][j],dp[p->v][k]+dp[son][j-k]); p = p->next; }num[son]++; dp[son][num[son]] = cost[son];}int main(){ int i,j,k,ta,tb; char a[MAX],b[MAX],temp[MAX*MAX]; while (gets(temp),temp[0] != '#') { sscanf(temp,"%d%d",&n,&m); Initial(); for (j = 1; j <= n; ++j) { //预处理 scanf("%s%d",a,&k); if (mmap.find(string(a)) == mmap.end()) mmap[string(a)] = tot++;; ta = mmap[string(a)]; cost[ta] = k; while (getchar() != '\n') { scanf("%s",b); if (mmap.find(string(b)) == mmap.end()) mmap[string(b)] = tot++; tb = mmap[string(b)]; vis[tb] = 1; AddEdge(ta,tb); //加边 } } for (i = 1; i <= n; ++i) if (vis[i] == 0) AddEdge(0,i);Tree_DP(0);for (i = m; i <= n; ++i)if (dp[0][i] < ans) ans = dp[0][i]; printf("%d\n",ans); } return 0;}/*10 4e 15 a b c da 10b 10c 10d 10f 1g 3h 3i 40j 16 f g h i10 1a 10b 10c 10d 10e 15 a b c df 0g 3h 3i 40j 16 f g h i3 2Aland 10Boland 20 AlandColand 153 0a 10b 10c 203 1a 10b 30c 20#*/

本文ZeroClock原创，但可以转载，因为我们是兄弟。