记录编号	24067	评测结果	AAAAAAAAAA
题目名称	319.[RQNOJ 184] 洞窟探索	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	0.199 s
提交时间	2011-03-28 09:37:58	内存使用	6.91 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=1555;
const int MAXM=1111;

struct edge
{
	int t,c;
	edge *p;
}e[MAXN],*v[MAXN];

int n,m,i,j,k,f[MAXN][MAXM],size[MAXN],ed[MAXN][3],tot=0,es=-1,sum[MAXN];
bool used[MAXN];

inline void addedge(int i,int j,int c)
{
	e[++es].t=j; e[es].c=c; e[es].p=v[i]; v[i]=e+es;
	used[j]=true; ++tot; ++sum[i];
}

void dp(int u,int p)
{
	int i,j,k;
	if (f[u][p]!=-1) return;
	if (v[u]==NULL || p==0)
	{
		f[u][p]=0;
		return;
	}
	if (sum[u]>1)
		for (i=max(0,p-1-size[v[u]->p->t]);i<=min(p-1,size[v[u]->t]);i++)
		{
			dp(v[u]->t,i);
			dp(v[u]->p->t,p-1-i);
		}
	else dp(v[u]->t,p-1);
	f[u][p]=1000000000;
	if (sum[u]==1) f[u][p]=f[v[u]->t][p-1]+v[u]->c*(p-1)*(m-p+1);
	if (sum[u]==2)
	{
		int tmp;
		j=v[u]->t;
		k=v[u]->p->t;
		for (i=max(0,p-1-size[k]);i<=min(p-1,size[j]);i++)
		{
			tmp=f[j][i]+f[k][p-1-i]+i*(m-i)*v[u]->c+(p-1-i)*(m-p+1+i)*v[u]->p->c;
			if (tmp<f[u][p]) f[u][p]=tmp;
		}
	}
}

int calsz(int u)
{
	size[u]=1;
	for (edge *x=v[u];x;x=x->p)
		size[u]+=calsz(x->t);
	return size[u];
}

int main()
{
	freopen("hole.in","r",stdin);
	freopen("hole.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<n;i++)
		scanf("%d%d%d",&ed[i][0],&ed[i][1],&ed[i][2]);
	used[1]=true;
	for (i=1;i<=n;i++)
		for (j=0;j<=m;j++)
			f[i][j]=-1;
	while (tot!=n-1)
	{
		for (i=1;i<n;i++)
			if (used[ed[i][0]]) addedge(ed[i][0],ed[i][1],ed[i][2]);
			else
				if (used[ed[i][1]]) addedge(ed[i][1],ed[i][0],ed[i][2]);
	}
	calsz(1);
	double r;
	r=(m-1)*m/2;
	dp(1,m);
	printf("%0.2lf",f[1][m]/r);
	return 0;
}