hdu2415(树上背包)

这道题好像没什么人写题解，于是写了一发

题意：有个坏蛋想要参加竞选，需要得到m个人的支持，买通第i个人(1<=i<=n)需要一个cost[i]，同时这些人又有上下属关系，只要买通了领导，他的下属（可以是下属的下属）也会给你投票，问最少要花多少钱

数据范围：N<=200,m<=n;

其实就是比较裸的树上分组背包，每个子节点的背包是一个组，选自己也是一个组，dfs搞一搞就好了，然而字符串处理实在恶心.....

#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
using namespace std;
const int MAX=1<<29;
int n,m;
map<string,int>dui;
vector<int>arr[205];
char str[100005],tmp[105];
int dp[205][205],fa[205],siz[205],cost[205],cnt=0;
void dfs1(int now)
{
int i,j;
siz[now]=1;
for(i=0;i<arr[now].size();i++)
{
int v=arr[now][i];
dfs1(v);
siz[now]+=siz[v];
}
}
void dfs(int now)
{
int i,j,k;
for(i=0;i<arr[now].size();i++)
{
dfs(arr[now][i]);
int v=arr[now][i];
for(j=m;j>=1;j--)for(k=1;k<=j;k++)dp[now][j]=min(dp[now][j],dp[now][j-k]+dp[v][k]);
}
if(now!=n+1)for(i=1;i<=min(m,siz[now]);i++)dp[now][i]=min(cost[now],dp[now][i]);
return ;
}
int main()
{
int i,j;
char ss[10];
while(scanf("%s",ss)!=EOF)
{
n=0;
cnt=0;
if(ss[0]=='#')return 0;
for(i=0;i<strlen(ss);i++)n*=10,n+=ss[i]-'0';
scanf("%d",&m);
int i,j;
for(i=0;i<=n+1;i++)arr[i].clear();
dui.clear();
getchar();
for(i=1;i<=n+1;i++)fa[i]=i;
for(i=0;i<n;i++)
{
gets(str);
int len=strlen(str);
for(j=0;j<len;j++)if(str[j]==' ')break;
int pos=j;
memset(tmp,0,sizeof(tmp));
for(j=0;j<pos;j++)tmp[j]=str[j];
string a=tmp;
if(!dui[a])dui[a]=++cnt;
int name1=dui[a],costs=0;
while(str[pos]>'9'||str[pos]<'0')pos++;
for(j=pos;;j++)
{
if(str[j]==''||str[j]>'9'||str[j]<'0')
{
pos=j;
break;
}
costs*=10;
costs+=str[j]-'0';
}
cost[name1]=costs;
int nums=0;
string b;
for(j=pos+1;j<len;j++)
{
if(str[j]!=' ')
{
tmp[nums++]=str[j];
if(str[j+1]==' '||str[j+1]=='')
{
tmp[nums++]='';
b=tmp;
nums=0;
if(!dui[b])dui[b]=++cnt;
int name2=dui[b];
arr[name1].push_back(name2);
fa[name2]=name1;
}
}
}
}
for(i=1;i<=n+1;i++)
{
dp[i][0]=0;
for(j=1;j<=m;j++)dp[i][j]=MAX;
}
for(i=1;i<=n;i++)if(fa[i]==i)arr[n+1].push_back(i);
dfs1(n+1);
dfs(n+1);
printf("%dn",dp[n+1][m]);
}
}
/*
9 5
A 45 B C
B 20
C 30
D 60 E F
E 20
F 50 G H
G 10
H 25 I
I 15
*/