首先建一个虚结点,权值为无穷大. 将入度为0的点与之相连, 然后做树形DP,为了防止重复,父亲单独考虑.详细见代码:
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<sstream>
using namespace std;
const int inf=1000000000;
vector<int> G[210];
int dp[210][210];
int cost[210],in_degree[210];
bool vis[210];
int n,m;
int min(int a,int b)
{
return a<b?a:b;
}
int dfs(int u)
{
int i,j,k,v;
int num=1;
vis[u]=1;
dp[u][0]=0;
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
if(vis[v]) continue;
num+=dfs(v);
}
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
for(j=n;j>=0;j--)
for(k=1;k<=n;k++)
{
if(j>=k&&dp[u][j]!=-1&&dp[u][j-k]!=-1&&dp[v][k]!=-1)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
else if(j>=k&&dp[u][j]==-1&&dp[u][j-k]!=-1&&dp[v][k]!=-1)
dp[u][j]=dp[u][j-k]+dp[v][k];
}
}
if(dp[u][num]!=-1&&dp[u][num]>cost[u])
dp[u][num]=cost[u];
else if(dp[u][num]==-1) dp[u][num]=cost[u];
return num;
}
int main()
{
int i,j;
char str[1000];
while(gets(str))
{
if(str[0]=='#') break;
sscanf(str,"%d%d",&n,&m);
for(i=0;i<=n;i++) G[i].clear();
map<string,int>graph;
memset(in_degree,0,sizeof(in_degree));
int id=0;
for(i=1;i<=n;i++)
{
scanf("%s",str);
if(graph.find(str)==graph.end()) graph[str]=++id;
int u=graph[str];
scanf("%d",&cost[u]);
gets(str);
stringstream ss(str);
string name;
while(ss>>name)
{
if(graph.find(name)==graph.end()) graph[name]=++id;
G[u].push_back(graph[name]);
in_degree[graph[name]]++;
}
}
cost[0]=inf;
for(i=1;i<=n;i++)
{
if(in_degree[i]) continue;
G[0].push_back(i);
}
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
dfs(0);
int ans=inf;
for(j=m;j<=n;j++)
if(dp[0][j]!=-1&&dp[0][j]<ans)
ans=dp[0][j];
printf("%d\n",ans);
}
//system("pause");
return 0;
}
posted on 2010-08-07 15:03
wuxu 阅读(168)
评论(0) 编辑 收藏 引用 所属分类:
动态规划