Beyond the Void
BYVoid
NOI 2003 数据生成器 (逃学的小孩)

可以知道,要使XY+YZ最大,XYZ三点都应该为树的叶节点(X可能特殊)。XYZ位置应该是一个三叉状,如下图所示。

Z
|
P--Y
|
X

假设XY,YZ路径交点(分离点)为P,则限制条件|XY|<=|XZ|可以化为|XP|+|YP| <= |XP|+|ZP|,进而得出|YP|<=|ZP|。而我们要求最大化的|XY|+|YZ|则为|XP|+2|YP|+|ZP|。设 S=|XP|+2|YP|+|ZP|。要想使S最大,应在|ZP|确定时尽量使|XP|+2|YP|最大,而|XP||YP|属于P的两棵不同的子树, 所以应该尽量让|YP|最大,|XP|<=|YP|。于是可以得出约束条件|XP|<=|YP|<=|ZP|

对于确定的P,S的值就是P的路径长度前三大的子树的路径长度之和。于是问题就转化为了在树中找到一个点P,使得由P出发相交与P点的三 条路径长度值和的最大,求出最大值。分析到这里,这个问题就可以用很简单的动态规划解决了。首先求出每棵子树中从根出发的最长路径的长度,记做H[i] (以i为根的子树)。接下来,再次从根节点出发,求出到每个节点的前三大的路径,特殊地X可以与P重合(也就是求前两大路径)。路径可以是子树之间过根节 点互联,也可以是与根节点的父节点相连。

时间复杂度为O(N)。

这道题我居然找到了两个版本,不知哪个是正宗的!?“数据生成器”还是“逃学的小孩”?

/* 
 * Problem: NOI2003 jerrygen
 * Author: Guo Jiabao
 * Time: 2009.5.23 14:20
 * State: Solved
 * Memo: 贪心 + 树形动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=200001,MAXM=MAXN*2;
using namespace std;
typedef long long Big;
struct edge
{
	edge *next;
	int t; Big c;
}ES[MAXM],*V[MAXN];
int N,M,EC;
Big H[MAXN],Ans;
inline void addedge(int a,int b,Big c)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
}
void init()
{
	int i,a,b,c;
	freopen("jerrygen.in","r",stdin);
	freopen("jerrygen.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<N;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
}
void CalcHeight(int i)
{
	H[i]=0;
	for (edge *e=V[i];e;e=e->next)
	{
		int j=e->t;
		if (H[j]==-1)
		{
			CalcHeight(j);
			if (H[j] + e->c > H[i])
				H[i] = H[j] + e->c;
		}
	}
}
void GetMaxChild(int i,int f,Big fl,int *M,Big *Max)
{
	Max[0]=Max[1]=Max[2]=M[0]=M[1]=M[2]=-1;
	Max[0]=fl; M[0]=f;
	for (edge *e=V[i];e;e=e->next)
	{
		int j=e->t;
		if (j!=f)
		{
			if (H[j] + e->c > Max[0])
			{
				Max[2]=Max[1];M[2]=M[1];
				Max[1]=Max[0];M[1]=M[0];
				Max[0] = H[j] + e->c;
				M[0] = j;
			}
			else if (H[j] + e->c > Max[1])
			{
				Max[2]=Max[1];M[2]=M[1];
				Max[1] = H[j] + e->c;
				M[1] = j;
			}
			else if (H[j] + e->c > Max[2])
			{
				Max[2] = H[j] + e->c;
				M[2] = j;
			}
		}
	}
}
void DP(int i,int f,Big fl)
{
	int M[3],j;
	Big Max[3],A,C;
	if (i==97)
		j=1;
	GetMaxChild(i,f,fl,M,Max);
	if (M[1]==-1)
		return;
	else if (M[2]==-1)
	{
		if (V[i]->t==f) V[i]=V[i]->next;
		j=V[i]->t;
		A=Max[0] + Max[1]*2;
		if (A>Ans)
			Ans=A;
		C=fl + V[i]->c;
		DP(j,i,C);
	}
	else
	{
		A=Max[0] + Max[1]*2 + Max[2];
		if (A>Ans)
			Ans=A;
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (j==f) continue;
			if (M[0]==j)
				C = Max[1] + e->c;
			else
				C = Max[0] + e->c;
			DP(j,i,C);
		}
	}
}
void solve()
{
	for (int i=1;i<=N;i++)
		H[i]=-1;
	CalcHeight(1);
	DP(1,0,0);
}
int main()
{
	init();
	solve();
	cout << Ans << endl;
	return 0;
}
<h2><span class="mw-headline">数据生成器 </span></h2>

【题目背景】

小明在做NOI2003练习赛的《幸福的老鼠》时觉得题目太简单了,于是对原题做了一些扩展:
  • 将原题的N从20扩展到200000。

  • 将原题经过一条街道需要的时间改为Ti(1 <= Ti <= 1000000000)分钟(i为街道的编号)。

  • 增加了一个条件:小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。

    即使这样,他仍然很快地做了出来。于是,小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图,不过为了增大测试数据的难度,他希望你能帮他选取一组X、Y、Z,使老鼠拿到礼物的时间尽可能地大。

    【小明扩展的题目(注意,你并不需要解决此题)】

    幸福的老鼠Jerry要过生日了,小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发,先到小狗家Y(因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离),再到大狗家Z,将两份礼物取回。 卡通城由N(3 <= N <= 200000)个居住点和N-1条连接居住点的双向街道组成,经过第i条街道需花费Ti(1 <= Ti <= 1000000000)分钟的时间。可以保证,任两个居住点间都存在通路。

    不妨设Jerry家在点X,小狗家在点Y,大狗家在点Z。现在,请你计算,Jerry最快需要耗费多长时间才能拿到生日礼物?

    【任务描述】

    定义:令|AB|表示卡通城中从A点走到B点需要的最少时间。

    给出卡通城的地图,找到一组X、Y、Z,使得:

  • |XY|≤|XZ|

  • |XY|+|YZ|最大。

    并求出此时|XY|+|YZ|的值。

    【输入文件】

    输入文件第一行是两个整数N(3 £ N £ 200000)和M(M=N-1),分别表示居住点总数和街道总数。从第2行开始到第N行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、 Ti(1£Ui, Vi £ N,1 £ Ti £ 1000000000),表示街道i连接居住点Ui和Vi,并且经过街道i需花费Ti分钟。

    【输出文件】

    输出文件仅包含一个整数T,即|XY|+|YZ|的最大值。

    【样例输入】

    4 3
      1 2 1
      2 3 1
      3 4 1

    【样例输出】

    4

附:

《逃学的小孩》

<h2><span>【问题描述】</span></h2>

<p class="MsoNormalIndent"><span lang="EN-US">Chris</span><span>家的电话铃响起了,里面传出了</span><span lang="EN-US">Chris</span><span>的老师焦急的声音:“喂,是</span><span lang="EN-US">Chris</span><span>的家长吗?你们的孩子又没来上课,不想参加考试了吗?”一听说要考试,</span><span lang="EN-US">Chris</span><span>的父母就心急如焚,他们决定在尽量短的时间内找到</span><span lang="EN-US">Chris</span><span>。他们告诉</span><span lang="EN-US">Chris</span><span>的老师:“根据以往的经验,</span><span lang="EN-US">Chris</span><span>现在必然躲在朋友</span><span lang="EN-US">Shermie</span><span>或</span><span lang="EN-US">Yashiro</span><span>家里偷玩《拳皇》游戏。现在,我们就从家出发去找</span><span lang="EN-US">Chris</span><span>,一但找到,我们立刻给您打电话。”说完砰的一声把电话挂了。</span></p>
<p class="MsoNormalIndent"><span lang="EN-US">Chris</span><span>居住的城市由</span><em><span lang="EN-US">N</span></em><span>个居住点和若干条连接居住点的双向街道组成,经过街道</span><em><span lang="EN-US">x</span></em><span>需花费</span><em><span lang="EN-US">T<sub>x</sub></span></em><span>分钟。可以保证,任两个居住点间有且仅有一条通路。</span><span lang="EN-US">Chris</span><span>家在点</span><span lang="EN-US">C</span><span>,</span><span lang="EN-US">Shermie</span><span>和</span><span lang="EN-US">Yashiro</span><span>分别住在点</span><span lang="EN-US">A</span><span>和点</span><span lang="EN-US">B</span><span>。</span><em><span><span lang="EN-US">Chris</span></span></em><em><span><span>的老师和</span><span lang="EN-US">Chris</span></span></em><em><span><span>的父母都有城市地图,但</span><span lang="EN-US">Chris</span></span></em><em><span><span>的父母知道点</span><span lang="EN-US">A</span></span></em><em><span><span>、</span><span lang="EN-US">B</span></span></em><em><span><span>、</span><span lang="EN-US">C</span></span></em><em><span><span>的具体位置而</span><span lang="EN-US">Chris</span></span></em><em><span><span>的老师不知</span></span></em><span>。</span></p>
<p class="MsoNormalIndent"><span>为了尽快找到</span><span lang="EN-US">Chris</span><span>,</span><span lang="EN-US">Chris</span><span>的父母会遵守以下两条规则:</span></p>
<p class="MsoNormalIndent"><span lang="EN-US"> </span></p>
<p class="MsoNormalIndent"><!--[if !supportLists]--><span lang="EN-US"><span>l<span> </span></span></span><!--[endif]--><span>如果</span><span lang="EN-US">A</span><span>距离</span><span lang="EN-US">C</span><span>比</span><span lang="EN-US">B</span><span>距离</span><span lang="EN-US">C</span><span>近,那么</span><span lang="EN-US">Chris</span><span>的父母先去</span><span lang="EN-US">Shermie</span><span>家寻找</span><span lang="EN-US">Chris</span><span>,如果找不到,</span><span lang="EN-US">Chris</span><span>的父母再去</span><span lang="EN-US">Yashiro</span><span>家;反之亦然。</span></p>
<p class="MsoNormalIndent"><!--[if !supportLists]--><span lang="EN-US"><span>l<span> </span></span></span><!--[endif]--><span lang="EN-US">Chris</span><span>的父母总沿着两点间唯一的通路行走。</span></p>
<p class="MsoNormalIndent"><span lang="EN-US"> </span></p>
<p class="MsoNormalIndent"><span>显然,</span><span lang="EN-US">Chris</span><span>的老师知道</span><span lang="EN-US">Chris</span><span>的父母在寻找</span><span lang="EN-US">Chris</span><span>的过程中会遵守以上两条规则,但由于他并不知道</span><span lang="EN-US">A</span><span>,</span><span lang="EN-US">B</span><span>,</span><span lang="EN-US">C</span><span>的具体位置,所以现在他希望你告诉他,最坏情况下</span><span lang="EN-US">Chris</span><span>的父母要耗费多长时间才能找到</span><span lang="EN-US">Chris</span><span>?</span></p>
<p class="MsoNormalIndent" align="center"><span lang="EN-US"><!--[if gte vml 1]><v:shapetype id="_x0000_t75"  coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe"  filled="f" stroked="f"> <v:stroke joinstyle="miter" /> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0" /> <v:f eqn="sum @0 1 0" /> <v:f eqn="sum 0 0 @1" /> <v:f eqn="prod @2 1 2" /> <v:f eqn="prod @3 21600 pixelWidth" /> <v:f eqn="prod @3 21600 pixelHeight" /> <v:f eqn="sum @0 0 1" /> <v:f eqn="prod @6 1 2" /> <v:f eqn="prod @7 21600 pixelWidth" /> <v:f eqn="sum @8 21600 0" /> <v:f eqn="prod @7 21600 pixelHeight" /> <v:f eqn="sum @10 21600 0" /> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" /> <o:lock v:ext="edit" aspectratio="t" /> </v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:3in;  height:2in' o:ole=""> <v:imagedata src="file:///C:DOCUME~1CMYKRG~1LOCALS~1Tempmsohtmlclip1�1clip_image001.emz" mce_src="file:///C:DOCUME~1CMYKRG~1LOCALS~1Tempmsohtmlclip1�1clip_image001.emz"   o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]--><!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Word.Picture.8" ShapeID="_x0000_i1025"   DrawAspect="Content" ObjectID="_1304617266"> </o:OLEObject> </xml><![endif]--></span></p>
<p class="MsoNormalIndent"><span>例如上图,这座城市由</span><span lang="EN-US">4</span><span>个居住点和</span><span lang="EN-US">3</span><span>条街道组成,经过每条街道均需花费</span><span lang="EN-US">1</span><span>分钟时间。假设</span><span lang="EN-US">Chris</span><span>住在点</span><span lang="EN-US">C</span><span>,</span><span lang="EN-US">Shermie</span><span>住在点</span><span lang="EN-US">A</span><span>,</span><span lang="EN-US">Yashiro</span><span>住在点</span><span lang="EN-US">B</span><span>,因为</span><span lang="EN-US">C</span><span>到</span><span lang="EN-US">B</span><span>的距离小于</span><span lang="EN-US">C</span><span>到</span><span lang="EN-US">A</span><span>的距离,所以</span><span lang="EN-US">Chiris</span><span>的父母会先去</span><span lang="EN-US">Yashiro</span><span>家寻找</span><span lang="EN-US">Chris</span><span>,一旦找不到,再去</span><span lang="EN-US">Shermie</span><span>家寻找。这样,最坏情况下</span><span lang="EN-US">Chris</span><span>的父母需要花费</span><span lang="EN-US">4</span><span>分钟的时间才能找到</span><span lang="EN-US">Chris</span><span>。</span></p>


<h2><span>【输入文件】</span></h2>

<p class="MsoNormalIndent"><span>输入文件</span><span lang="EN-US">hookey.in</span><span>第一行是两个整数</span><em><span lang="EN-US">N</span></em><span>(</span><span lang="EN-US">3 </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> <em>N</em> </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> 200000</span><span>)和</span><em><span lang="EN-US">M</span></em><span>,分别表示居住点总数和街道总数。以下</span><em><span lang="EN-US">M</span></em><span>行,每行给出一条街道的信息。第</span><em><span lang="EN-US">i+1</span></em><span>行包含整数</span><em><span lang="EN-US">U<sub>i</sub></span></em><span>、</span><em><span lang="EN-US">V<sub>i</sub></span></em><span>、</span><em><span lang="EN-US">T<sub>i</sub></span></em><span>(</span><span lang="EN-US">1</span><span lang="EN-US"><span>£</span></span><em><span lang="EN-US">U<sub>i</sub></span></em><span lang="EN-US">, <em>V<sub>i</sub></em> </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> <em>N</em></span><span>,</span><span lang="EN-US">1 </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> <em>T<sub>i</sub></em> </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> 1000000000</span><span>),表示街道</span><em><span lang="EN-US">i</span></em><span>连接居住点</span><em><span lang="EN-US">U<sub>i</sub></span></em><span>和</span><em><span lang="EN-US">V<sub>i</sub></span></em><span>,并且经过街道</span><em><span lang="EN-US">i</span></em><span>需花费</span><em><span lang="EN-US">T<sub>i</sub></span></em><span>分钟。街道信息不会重复给出。</span></p>


<h2><span>【输出文件】</span></h2>

<p class="MsoNormalIndent"><span>输出文件</span><span lang="EN-US">hookey.out</span><span>仅包含整数</span><em><span lang="EN-US">T</span></em><span>,即最坏情况下</span><span lang="EN-US">Chris</span><span>的父母需要花费</span><span lang="EN-US">T</span><span>分钟才能找到</span><span lang="EN-US">Chris</span><span>。</span></p>


<h2><span>【样例输入】</span></h2>

<p class="a"><span lang="EN-US">4 3</span></p>
<p class="a"><span lang="EN-US">1 2 1</span></p>
<p class="a"><span lang="EN-US">2 3 1</span></p>
<p class="a"><span lang="EN-US">3 4 1</span></p>


<h2><span>【样例输出】</span></h2>

<p class="a"><span lang="EN-US">4</span></p>

上次修改时间 2017-05-26

相关日志