一道树形背包,考的却是对STL的运用
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<iostream>
#define gc getchar()
using namespace std;
const int N=205;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
map<string,int>mp;int n,m;char s[N];
struct edge{int y,next;}a[N<<1];int len,last[N],d[N],c[N],fa[N],f[N][N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void treedp(int x)
{
c[x]=1;f[x][0]=0;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y==fa[x])continue;
treedp(y);c[x]+=c[y];
int ms=min(c[x],m);
for(int i=ms;i>=1;i--)
{
int mt=min(c[y],i);
for(int j=mt;j>=1;j--)if(f[y][j]!=0x3f3f3f3f)
{
f[x][i]=min(f[x][i],f[y][j]+f[x][i-j]);
}
}
}
int ms=min(c[x],m);
if(x)for(int i=1;i<=ms;i++)f[x][i]=min(f[x][i],d[x]);//选自己
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
int id=0;
len=0;memset(last,0,sizeof(last));
memset(c,0,sizeof(c));memset(fa,0,sizeof(fa));
memset(f,0x3f,sizeof(f));
mp.clear();
for(int i=1;i<=n;i++)
{
scanf("%s",s);
if(!mp[s])mp[s]=++id;
int x=mp[s];scanf("%d",&d[x]);
while(gc==' ')
{
scanf("%s",s);if(!mp[s])mp[s]=++id;
int y=mp[s];fa[y]=x;
}
}
for(int i=1;i<=n;i++)ins(fa[i],i);
treedp(0);
qw(f[0][m]);puts("");
n=0;m=0;
}
return 0;
}
/*
3 2
Aland 10
Boland 20 Aland
Coland 15
#
*/
最后一次更新于2019-10-25
0 条评论