题目链接:http://poj.org/problem?id=3345
题目大意及思路:用最少的钱去收买m个国家,但国家这间有附属关系,如果收买了一个国家,它的附属国也被收买了,做法树形dp+背包,状态转移方程是:dp[u][k]=min(dp[u][k],dp[v][j]+dp[u][k-j]);
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<string> #include<sstream> #include<queue> #include<algorithm> #include<vector> #include<stack> #include<list> #include<iostream> #include<map> using namespace std; #define inf 0x3f3f3f3f #define Max 110 int max(int a,int b) { return a>b?a:b; } inline int min(int a,int b) { return a<b?a:b; } char str[20100]; char con[110]; int val[220]; int n,m; int dp[220][220],eid; map<string,int>mp; int p[220],num[220],pre[220]; struct node { int to,next; }e[2100]; inline void addedge(int u,int v) { e[eid].to=v; e[eid].next=p[u]; p[u]=eid++; } void dfs(int u) { int i,j,k,v; num[u]=1; dp[u][0]=0; for(i=p[u];i!=-1;i=e[i].next) { v=e[i].to; dfs(v); for(k=n;k>=0;k--) { for(j=1;j<=k;j++) dp[u][k]=min(dp[u][k],dp[v][j]+dp[u][k-j]); } num[u]+=num[v]; } dp[u][num[u]]=val[u]; } int main() { stringstream s; int i,j,sum; while(gets(str)) { if(str[0]=='#') break; mp.clear(); eid=0; sum=0; memset(p,-1,sizeof(p)); memset(num,0,sizeof(num)); memset(pre,0,sizeof(pre)); sscanf(str,"%d%d",&n,&m); int id=1; for(i=1;i<=n;i++) { gets(str); s.clear(); s.str(str); s>>con; int tmp=mp[con]; if(!tmp) mp[con]=id++; tmp=mp[con]; s>>val[tmp]; sum+=val[tmp]; while(s>>con) { if(!mp[con]) mp[con]=id++; addedge(tmp,mp[con]); pre[mp[con]]=tmp; } } for(i=1;i<=n;i++) { if(pre[i]==0) addedge(0,i); } for(i=0;i<=n;i++) for(j=0;j<=n;j++) dp[i][j]=inf; dfs(0); int ans=dp[0][m]; for(i=m;i<=n;i++) { if(dp[0][i]<ans) ans=dp[0][i]; } printf("%d\n",ans); } }