Beyond the Void
BYVoid
AHOI 洞窟探索

题目中隐含条件告诉我们这是一棵二叉树,接下来树形动态规划。显然选定的M个节点一定为一棵子树,不可能为多个连通块,因为这样最小。

设状态F[i,a]表示以i为根的子树中,分配a个点的最小总价值。

状态转移方程

当i为叶节点

F[i,1]=0 F[i,a]=无穷大 (a>1)

当i只有一个子节点

F[i,a]=F[i.left,a-1] + (a-1)*(m-(a-1))*w(i,i.left)

当i有两个子节点

F[i,a]=min{ F[i.left,b] + F[i.right,a-1-b] + b*(m-b)w(i,i.left) + (a-1-b)(m-(a-1-b))*w(i,i.right)}

0<=b<=a-1 且 b<=i.left.size , b<=i.right.size size 为子树的节点总个数

时间复杂度为O(N*M^2)

/* 
 * Problem: HAOI2008 hole
 * Author: Guo Jiabao
 * Time: 2009.4.21 19:41
 * State: Solved
 * Memo: 树形动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1501,MAXM=1001,INF=0x7FFFFFFF;
using namespace std;
struct edge
{
	edge *next;
	int t,w;
}ES[MAXN*2],*V[MAXN];
struct node
{
	node *child[2];
	int size,w[2],c;
}P[MAXN];
int N,M,EC;
int F[MAXN][MAXM];
double As;
inline void addedge(int a,int b,int w)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->w=w;
}
void build(node &p,int f)
{
	int i=&p-P,j;
	p.c=0;
	p.size=1;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (j==f) continue;
		p.w[p.c]=e->w;
		build(P[j],i);
		p.child[p.c]=P+j;
		p.size += p.child[p.c]->size;
		p.c++;
	}
}
void init()
{
	int i,a,b,c;
	freopen("hole.in","r",stdin);
	freopen("hole.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N-1;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
		addedge(b,a,c);
	}
	build(P[1],0);
	memset(F,-1,sizeof(F));
}
int dp(int i,int a)
{
	if (F[i][a]==-1)
	{
		int rs,j,k;
		if (a==0)
			rs=0;
		else
		{
			if (P[i].c==0)
			{
				if (a==1)
					rs=0;
				else
					rs=INF;
			}
			else if (P[i].c==1)
			{
				rs=(a-1)*(M-(a-1))*P[i].w[0];
				j=P[i].child[0] - P;
				rs+=dp(j,a-1);
			}
			else
			{
				int b=0,ra;
				j=P[i].child[0] - P; k=P[i].child[1] - P;
				if (a - 1 - P[k].size >b)
					b=a - 1 - P[k].size;
				for (rs=INF;b<=a-1 && b<=P[j].size;b++)
				{
					ra = dp(j,b) + dp(k,a-1-b);
					ra += b*(M-b) * P[i].w[0];
					ra += (a-1-b)*(M-(a-1-b)) * P[i].w[1];
					if (ra<rs)
						rs=ra;
				}
			}
		}
		F[i][a]=rs;
	}
	return F[i][a];
}
void solve()
{
	int Ans=dp(1,M);
	double sum=(double)M*(M-1)/2.0;
	As=Ans / sum;
}
int main()
{
	init();
	solve();
	printf("%.2lfn",As);
	return 0;
}
<div class="MainText">
<div><strong>题目背景: </strong></div>
<div>LSZ小朋友组织了一支天文爱好队,他们这次要去探索一个洞窟(天文爱好者怎么探索洞窟?!?),因为据说那里是一个神秘的地方,是地球上最容易捕捉到来自宇宙信息的场所。小朋友带领他的天文爱好队以及许多先进设备来到了洞窟……</div>
<div><strong>题目描述: </strong></div>
<div>洞窟由许许多多的洞穴和通道组成,且任意两个洞穴间有且只有一条路经,每条路经的长度不一定相同。从入口可以进入 1号洞穴,且1号洞穴是唯一与入口相连的洞穴。由于设备有限,小朋友只能在某些洞穴设置他的设备(一个洞穴设一个就足够了)。为了防止迷路,天文爱好队的 成员一致决定,每到一个洞窟,就在这里设置一个设备,并留一人看守。</div>
<div>这些设备工作时,任意两个设备间需要通信。通信耗费的时间与这两个洞穴之间的距离有关(指通过通道连接的距离,非两点间距离)。如果有 m个设备,那么共有m*(m-1)/2条路经连接任意两个不同的设备,现在小朋友想知道,选择哪些洞穴,可以使得这些路径的平均长度最小。</div>
<div>平均长度即∑ dist(i,j)/sum,dist(i,j)与dist(j,i)两者只算其中一者(即每两点间的路径长只算一遍),sum:=m*(m-1)/2。</div>
<div>注意:为了使问题简化,我们假设任何一个洞穴最多与另外三个洞穴直接有通道相连。 1号洞穴最多只与两个洞穴直接有通道相连。</div>
<div><strong>输入: </strong></div>
<div>第一行两个整数 n和m,表示洞穴总数和设备数。</div>
<div>以下 n-1行,每行3个整数x y 和 l,表示一条连接x 和 y 洞穴的通道,长度为l。</div>
<div><strong>输出: </strong></div>
<div>仅一行,一个数:表示最小的平均长度。(保留到小数点后 2位)</div>
<div><strong>输入样例: </strong></div>
<div>4 3</div>
<div>1 2 1</div>
<div>1 3 2</div>
<div>2 4 1</div>
<div><strong>输出样例: </strong></div>
<div>1.33</div>
<div><strong>数据规模: </strong></div>
<div>n&lt;=1500,m&lt;=1000,m&lt;=n</div>
<div>保证每条通道的长度为正,且运算过程中不会有超过 longint的情况(在算法正确时)</div>
<div><strong>样例解释: </strong></div>
<div>选择 1、2、4号洞穴,总路径长1+1+2=4,平均长度:4/3=1.33</div>
</div>

上次修改时间 2017-02-03

相关日志