T2 .tyvj P1523贪吃的九头龙
描述
传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。
有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。
这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。
对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。
九头龙希望它的“难受值”尽量小，你能帮它算算吗？
格式
输入格式
输入的第1行包含三个整数N(1<=N<=300)，M(2<=M<=N)，K(1<=K<=N)。N个果子依次编号1,2,...,N，且最大的果子的编号总是1。第2行到第N行描述了果树的形态，每行包含三个整数a(1<=a<=N)，b(1<=b<=N)，c(0<=c<=105)，表示存在一段难受值为c的树枝连接果子a和果子b。
输出格式
输出仅有一行，包含一个整数，表示在满足“大头”的要求的前提下，九头龙的难受值的最小值。如果无法满足要求，输出-1。
样例1
样例输入1
8 2 4
1 2 20
1 3 4
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5
样例输出1
4
分析：
爆搜搜了20分
正解：树形DP
题目可以分为m=2和m>2的情况，因为当m>2是，小头一定不会产生难受值，只关心大头就可以，而当m=2时，小头要选择出大头选的k个之外的所有果子，把题目当作两个头来做。
注意事先用左儿子右兄弟表示法转换成一棵二叉树。
fa代表父亲，val是难受值，ch是左儿子和右兄弟。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#define M 310
#define INF 100000000
using namespace std;
int fa[M],val[M][M],ch[M][],f[M][M][],head[M],n,m,k;
struct node
{
int v,pre,t;
};node e[M*];
void add(int i,int x,int y,int z)
{
e[i].v=y;
e[i].t=z;
e[i].pre=head[x];
head[x]=i;
}
void build(int x)
{
for(int i=head[x];i;i=e[i].pre)
if(!fa[e[i].v])
{
fa[e[i].v]=x;
if(!ch[x][])ch[x][]=e[i].v;
else
{
int f=ch[x][];
while(ch[f][])f=ch[f][];
ch[f][]=e[i].v;
}
build(e[i].v);
}
}
int dfs1(int now,int sum,int p)//now是当前节点，sum是大头还有几个没选，p是now的父亲有没有选
{
if(f[now][sum][p]!=-)return f[now][sum][p];
if(now==&&sum>)return INF;
if(now==&&sum==)return ;
int minn=INF;
for(int i=;i<=sum;i++)//大头不选
{
int tot=;
if(p==)tot+=val[now][fa[now]];
tot+=dfs1(ch[now][],i,)+dfs1(ch[now][],sum-i,p);
minn=min(minn,tot);
}
for(int i=;i<sum;i++)//大头选
{
int tot=;
if(p==)tot+=val[now][fa[now]];
tot+=dfs1(ch[now][],i,)+dfs1(ch[now][],sum-i-,p);
minn=min(minn,tot);
}
f[now][sum][p]=minn;
return f[now][sum][p];
}
int dfs2(int now,int sum,int p)//now是当前节点，sum是大头还有几个没选，p是now的父亲有没有选
{
if(f[now][sum][p]!=-)return f[now][sum][p];
if(sum==)return ;
if(now==)return INF;
int minn=INF;
for(int i=;i<=sum;i++)//大头不选
minn=min(minn,dfs2(ch[now][],i,)+dfs2(ch[now][],sum-i,p));
for(int i=;i<sum;i++)//大头选
{
int tot=;
if(p==)tot+=val[now][fa[now]];
tot+=dfs2(ch[now][],i,)+dfs2(ch[now][],sum-i-,p);
minn=min(minn,tot);
}
f[now][sum][p]=minn;
return f[now][sum][p];
}
int main()
{
freopen("jh.in","r",stdin);
memset(f,-,sizeof(f));
scanf("%d%d%d",&n,&m,&k);
if(n-k<m-){printf("-1");return ;}
for(int i=;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
val[x][y]=val[y][x]=z;
add(i*-,x,y,z);
add(i*,y,x,z);
}
fa[]=;build();
if(m==)//考虑大头小头一起选
{
int ans=INF;
for(int i=;i<k;i++)
ans=min(ans,dfs1(ch[][],i,)+dfs1(ch[][],k-i-,));
printf("%d",ans);
}
else//只考虑选大头的情况
{
int ans=INF;
for(int i=;i<k;i++)
ans=min(ans,dfs2(ch[][],i,)+dfs2(ch[][],k-i-,));
printf("%d",ans);
}
return ;
}