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>

相關日誌