AHOI 洞窟探索
本文正體字版由OpenCC轉換
題目中隱含條件告訴我們這是一棵二叉樹，接下來樹形動態規劃。顯然選定的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<=1500,m<=1000，m<=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