记录编号	9829	评测结果	AAAAAAAAAA
题目名称	[RQNOJ 184] 洞窟探索	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	1.315 s
提交时间	2009-04-21 16:43:33	内存使用	16.01 MiB

#include <iostream>

using namespace std;

#define MAXN 1550
#define MAXM 1110
#define INF 999999999

int n,m,son[MAXN][3],data[MAXN][MAXN],many[MAXN],f[MAXN][MAXM];
double ans;
bool vis[MAXN];

inline int MIN(int a,int b)
{
	return a<b?a:b;
}

void dp(int x,int i)
{
	if (i==0 || son[x][0]==0)
	{
		f[x][i]=0;
		return;
	}
	int a,b,s1,s2,p1,p2,now,min;
	s1=son[x][0];s2=son[x][1];
	p1=data[x][s1];p2=data[x][s2];
	f[x][i]=INF;
	if (s2==0)
	{
		if (f[s1][i-1]==-1)
			dp(s1,i-1);
		if (f[s1][i-1]<INF)		
			f[x][i]=f[s1][i-1]+(i-1)*(m-i+1)*p1;
	}
	else
	{
		min=MIN(i-1,many[s1]);
		for (a=0;a<=min;a++)
		{
			b=i-1-a;
			if (b>many[s2])
				continue;
			if (f[s1][a]==-1)
				dp(s1,a);
			if (f[s2][b]==-1)
				dp(s2,b);
			if (f[s1][a]>=INF || f[s2][b]>=INF)
				continue;
			now=f[s1][a]+a*(m-a)*p1;
			now+=f[s2][b]+b*(m-b)*p2;
			if (now<f[x][i])
				f[x][i]=now;
		}
	}

}

int dfs(int x)
{
	int y,s=0;
	vis[x]=true;
	many[x]=1;
	for (y=1;y<=n;y++)
		if (data[x][y]!=-1)
			if (!vis[y])
			{
				son[x][s++]=y;
				many[x]+=dfs(y);
			}
	return many[x];
}

void run()
{
	double sum;
	dfs(1);
	dp(1,m);
	sum=m*(m-1);
	sum/=2;
	ans=f[1][m]/sum;
}

void ini()
{
	int i,j,a,b,t;
	for (i=0;i<MAXN;i++)
		for (j=0;j<MAXN;j++)
		{
			data[i][j]=-1;
		}
	for (i=0;i<MAXN;i++)
		for (j=0;j<MAXM;j++)
			f[i][j]=-1;
	cin>>n>>m;
	for (i=1;i<n;i++)
	{
		cin>>a>>b>>t;
		data[a][b]=data[b][a]=t;
	}
}

int main()
{
	freopen("hole.in","r",stdin);
	freopen("hole.out","w",stdout);
	ini();
	if (m<=1)
		ans=0;
	else
		run();
	printf("%.2lf",ans);
	return 0;
}