题目连接：http://acm.hust.edu.cn/vjudge/problem/17665
参考资料：http://blog.csdn.net/woshi250hua/article/details/7684771
题目大意：xx大佬要竞选xx职位，现一共有n个国家，获得xx职位至少需要m个国家的支持，某个国家下面会有若干个附属国家，这个代表获得这个国家的支持就可以获得一群国家的支持。想要获得这个国家的支持，就必须拿钻石去贿赂，好厚黑。问获得xx职位最少需要多少钻石。
这道题有几个要点：
这里不是一棵树，而是一个森林。所以要记录所有根节点，并添加一个主根
for(i=;i<=n;i++) if(!vis2[i]) add(,i);
选了根节点就等同于选了所有的子节点，为了实现这个需要注意两个地方
先看代码
void dfs(int rt)
{
vis[rt]=;
num[rt]=dp[rt][]=;
for(int i = head[rt];i!=-;i=tree[i].next)
{
int y = tree[i].y;
if(vis[y]) continue;
dfs(y);
num[rt]+=num[y];
for(int j=num[rt];j>=;j--)
{
for(int k=;k<=j;k++)
{
dp[rt][j] = min(dp[rt][j],dp[rt][j-k]+dp[y][k]);
}
}
}
num[rt]++;
dp[rt][num[rt]] = cost[rt];
}
- num[rt]一开始初始化为0，到了最后才+1，这是因为同时选根节点和子节点已经没有意义了，所以对于一个根只需要遍历子节点的情况，并在最后将选了根节点的情况加入即可。
- 在第二个循环里，如果选子必选根，则K<J；如果选子和选根没关系，则K<=J，即根可以为0
输入：
这里一开始输入两个数字，却是用#结束，怎么办？
两种思路：1.字符串转数字。2.用sscanf。
输入没有给定数量，通过换行结束怎么办？
用getchar()判断换行符号，不是换行符号就接着输入
其他的和一般的树形DP没什么区别，完整代码如下：
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!\n")
#define MAXN 200+5
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f int n,m; struct node{int y,val,next;}tree[MAXN<<]; int head[MAXN],vis[MAXN],ptr=,val[MAXN],dp[MAXN][MAXN]; int cost[MAXN],vis2[MAXN],num[MAXN]; map<string,int> mmap; void init()
{
mem(head,-);
mem(vis,);
mem(dp,INF);
mem(vis2,);
ptr=;
mmap.clear();
}
void add(int x,int y)
{
tree[ptr].y = y;
tree[ptr].next = head[x];
head[x] = ptr++;
} void dfs(int rt)
{
vis[rt]=;
num[rt]=dp[rt][]=;
for(int i = head[rt];i!=-;i=tree[i].next)
{
int y = tree[i].y;
if(vis[y]) continue;
dfs(y);
num[rt]+=num[y];
for(int j=num[rt];j>=;j--)
{
for(int k=;k<=j;k++)
{
dp[rt][j] = min(dp[rt][j],dp[rt][j-k]+dp[y][k]);
}
}
}
num[rt]++;
dp[rt][num[rt]] = cost[rt];
} int main()
{
int i,j,k;
char tmp[],a[],b[];
while(gets(tmp) && tmp[]!='#')
{
sscanf(tmp,"%d%d",&n,&m);
init();
int tot=,ta,tb,ans=INF;
for(i=;i<=n;i++)
{
sf("%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')
{
sf("%s",b);
if(mmap.find(string(b))==mmap.end())
mmap[string(b)] = tot++;
tb = mmap[string(b)];
add(ta,tb);
add(tb,ta);
vis2[tb] = ;
}
}
for(i=;i<=n;i++)
{
if(!vis2[i]) add(,i);
}
dfs();
for(i=m;i<=n;i++) ans = min(ans,dp[][i]);
pf("%d\n",ans);
}
}