NOI 2006 網絡收費

對於我來說，這道題不易想到是動態規劃，即使想到了，實現也是不容易的。

首先仔細觀察表格可以發現一個等價的轉化。假設一對付費節點i,j的最近公共祖先爲p，如果p的nA<nB，稱p爲A付費節點，否則 爲B付費節點。對於i和p，如果i和p的節點性質相同，則需要一倍的付費，j也相同。這時候，i,j的付費可以獨立考慮了。這種付費方式與原題描述是等價 的。這一步是動態規劃的必要前提條件。

經過這一步的轉化，問題就明瞭多了。問題可以被描述爲，安排每個葉節點的付費方案，使每個節點到其所有祖先需要付費之和最小。考慮一個葉 節點i到每個祖先p需要付費多少，取決於i相對於p的另一棵子樹中所有節點j與i的流量F[i,j]之和。定義Cost[i,k]爲葉節點i到其第k個祖 先需要的付費，我們可以求出每兩個葉節點i,j的最近公共祖先p，並令Cost[i,p]和Cost[j,p]的值增加F[i,j]。

定義狀態DP[i,j,k]爲以第i個節點爲根的子樹中分配j個A節點，從根節點到i的每個祖先的狀態集合爲k的最小費用。k可以用二進制位表示，如果一個節點nA<nB，則標記該節點狀態爲A付費節點。狀態轉移方程爲

F[i,j,k] = Min{ F[i.left,a,k+this] + F[i.right,j-a,k+this] }

其中 k+this表示加上當前節點狀態

對於邊界狀態，就是i爲葉節點，計算方法就是i的所有父節點中與i狀態相同的節點k的Cost[i,k]之和，如果i與原先付費方式不同，還要加上C[i]。

觀察發現F[i,j,k]的取值範圍都是0..2^N，如果直接這樣寫，對於2^10會超空間的，只能拿到80%的分，直觀難以發現如何減 少狀態數，實際上後兩維是有浪費的。假設葉節點爲第0層，根節點爲第N層，那麼對於第k層的節點，它能控制的葉節點的個數最多爲2^k，於是j的取值範圍 就是0..2^k，一共有2^k + 1種可能。它的祖先一共有N-k個，每個祖先個狀態可能有兩種，於是k的取值一共有2^(N-k)種可能。因此，j,k的取值一共有(2^k + 1) * (2^(N-k)) = 2^N + 2^(N-k) <=2^(N+1)個，於是我們就可以把後兩維狀態數壓縮到2^(N+1)，這樣就不會超過空間限制了。兩維的具體壓縮方法可以看成是兩個二進制數 連接到一起。

/* 
 * Problem: NOI2006 network
 * Author: Guo Jiabao
 * Time: 2009.6.3 16:34
 * State: Solved
 * Memo: 樹形動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=11,MAXM=1025,MAXP=MAXM*2,INF=0x7FFFFFFF / 4;
struct Rec
{
    int r[MAXP],lim;
    int get(int a,int b)
    {
        int c=a*lim + b;
        return r[c];
    }
    void set(int a,int b,int v)
    {
        int c=a*lim + b;
        r[c]=v;
    }
}Record[MAXP];
int N,M,Ac,Ans,NewAns;
int Ancestor[MAXM][MAXN],Cost[MAXM][MAXN],Flow[MAXM][MAXM];
int Convert[MAXM];
bool Type[MAXM],mark;
void init()
{
    int i,j,a;
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    scanf("%d",&N);
    M=1 << N;
    for (i=1;i<=M;i++)
    {
        scanf("%d",&a);
        Type[i] = a==0;
    }
    for (i=1;i<=M;i++)
        scanf("%d",&Convert[i]);
    for (i=1;i<=M-1;i++)
    {
        for (j=i+1;j<=M;j++)
        {
            scanf("%d",&a);
            Flow[i][j]=Flow[j][i]=a;
        }
    }
    Ans = INF;
}
int Brink(int a,int na,int S)
{
    int i,Ca=0,Cb=0;
    for (i=1;i<=N;i++,S=(S>>1))
    {
        if (S & 1)
            Ca += Cost[a][i];
        else
            Cb += Cost[a][i];
    }
    if (na==1)
        return Ca + (Type[a]?0:Convert[a]);
    else
        return Cb + (Type[a]?Convert[a]:0);
}
int DP(int i,int j,int k,int height)
{
    int rs=Record[i].get(j,k);
    if (rs==0)
    {
        if (height)
        {
            rs=INF;
            int newrs,a,ls,tk;
            mark=j < ((1 << height) - j);
            tk=(k << 1) + mark;
            ls=1<<(height-1);
            if ((a=j-ls)<0) a=0;
            for (;a<=j && a<=ls;a++)
            {
                newrs  = DP(i << 1,a,tk,height-1);
                newrs += DP((i << 1) + 1,j-a,tk,height -1);
                if (newrs < rs)
                    rs = newrs;
            }
        }
        else
            rs = Brink(i-M+1,j,k);
        Record[i].set(j,k,rs);
    }
    return rs;
}
void solve()
{
    int i,j,k,l,p,a,b,NewAns;
    for (i=1;i<=M;i++)
    {
        k=i+M-1;
        for (j=1;j<=N;j++)
        {
            k=k >> 1;
            Ancestor[i][j]=k;
        }
    }
    for (k=1;k<=N+1;k++)
    {
        a=1 << (k-1);
        b=(1 << k) -1;
        l=N-k+1;
        for (p=a;p<=b;p++)
        {
            Record[p].lim=1 << (N-l);
            memset(Record[p].r,0,sizeof(Record[p].r));
        }
    }
    for (i=1;i<=M;i++)
    {
        for (j=i+1;j<=M;j++)
        {
            for (k=1;k<=N;k++)
            {
                if (Ancestor[i][k] == Ancestor[j][k])
                {
                    Cost[i][k] += Flow[i][j];
                    Cost[j][k] += Flow[i][j];
                    break;
                }
            }
        }
    }
    for (i=0;i<=M;i++)
    {
        NewAns = DP(1,i,0,N);
        if (NewAns < Ans)
            Ans = NewAns;
    }
}
int main()
{
    init();
    solve();
    printf("%dn",Ans);
    return 0;
}

【問題描述】

網絡已經成爲當今世界不可或缺的一部分。每天都有數以億計的人使用網絡進行學習、科研、娛樂等活動。然而，不可忽視的一點就是網絡本身有着 龐大的運行費用。所以，向使用網絡的人進行適當的收費是必須的，也是合理的。 MY 市NS 中學就有着這樣一個教育網絡。網絡中的用戶一共有2N 個，編號依次爲1, 2, 3, …, 2^N。這些用戶之間是用路由點和網線組成的。用戶、路由點與網線共同構成一個滿二叉樹結構。樹中的每一個葉子結點都是一個用戶，每一個非葉子結點（灰 色）都是一個路由點，而每一條邊都是一條網線（見下圖，用戶結點中的數字爲其編號）。

<a class="image" title="Image:Networkcost1.png" href="http://www.ruvtex.cn/wiki/Image:Networkcost1.png"><img src="http://www.ruvtex.cn/mw/images/4/47/Networkcost1.png" alt="Image:Networkcost1.png" width="533" height="304" /></a>

MY 網絡公司的網絡收費方式比較奇特，稱爲“ 配對收費 ”。即對於每兩個用戶i, j (1≤i &lt; j ≤2^N ) 進行收費。由於用戶可以自行選擇兩種付費方式A、B中的一種，所以網絡公司向學校收取的費用與每一位用戶的付費方式有關。該費用等於每兩位不同用戶配對產 生費用之和。

爲了描述方便，首先定義這棵網絡樹上的一些概念：
  • 祖先：根結點沒有祖先，非根結點的祖先包括它的父親以及它的父親的祖先；
  • 管轄葉結點：葉結點本身不管轄任何葉結點，非葉結點管轄它的左兒子所管轄的葉結點與它的右兒子所管轄的葉結點；

  • 距離：在樹上連接兩個點之間的用邊最少的路徑所含的邊數。

    對於任兩個用戶i, j (1≤i<j≤2^N )，首先在樹上找到與它們距離最近的公共祖先：路由點P，然後觀察P 所管轄的葉結點（即用戶）中選擇付費方式A 與B的人數，分別記爲nA 與nB，接着按照網絡管理條例第X 章第Y 條第Z 款進行收費（如下表），其中Fi, j 爲i 和j 之間的流量，且爲已知量。

    Image:Networkcost2.png

    由於最終所付費用與付費方式有關，所以NS 中學的用戶希望能夠自行改變自己的付費方式以減少總付費。然而，由於網絡公司已經將每個用戶註冊時所選擇的付費方式記錄在案，所以對於用戶i，如果他/她 想改變付費方式（由A 改爲B 或由B 改爲A），就必須支付Ci 元給網絡公司以修改檔案（修改付費方式記錄）。

    現在的問題是，給定每個用戶註冊時所選擇的付費方式以及Ci，試求這些用戶應該如何選擇自己的付費方式以使得NS 中學支付給網絡公司的總費用最少（更改付費方式費用+配對收費的費用）。

    【輸入文件】

    輸入文件中第一行有一個正整數N。

    第二行有2N 個整數，依次表示1 號，2 號，…，2^N 號用戶註冊時的付費方式，每一個數字若爲0，則表示對應用戶的初始付費方式爲A，否則該數字爲1，表示付費方式爲B。

    第三行有2N 個整數，表示每一個用戶修改付費方式需要支付的費用，依次爲C1, C2, …,CM 。( M=2^N ) 以下2^N-1 行描述給定的兩兩用戶之間的流量表F，總第(i + 3)行第j 列的整數爲Fi, j+i 。（1≤i<2^N，1≤j≤2^N – i） 所有變量的含義可以參見題目描述。

    【輸出文件】

    你的程序只需要向輸出文件輸出一個整數，表示NS 中學支付給網絡公司的最小總費用。（單位：元）

    【樣例輸入】 

    2
  1 0 1 0
  2 2 10 9
  10 1 2
  2 1
  3
    【樣例輸出】 
    8
    【樣例說明】

    將1 號用戶的付費方式由B 改爲A，NS 中學支付給網絡公司的費用達到最小。

    【評分方法】

    本題沒有部分分，你的程序的輸出只有和我們的答案完全一致才能獲得滿分，否則不得分。

    【數據規模和約定】

  • 40%的數據中N≤4；

  • 80%的數據中N≤7；
  • 100%的數據中N≤10，0≤Fi, j≤500，0≤Ci≤500 000。

相關日誌