NOI 2003 數據生成器 (逃學的小孩)
本文正體字版由OpenCC轉換
可以知道，要使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