NOI 2006 网络收费

This post is written in Chinese. Please consider using Google Translate

对于我来说，这道题不易想到是动态规划，即使想到了，实现也是不容易的。

首先仔细观察表格可以发现一个等价的转化。假设一对付费节点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。

Related posts