BZOJ3090 [Coci2009]podjela

DarkBzoj提交地址

题意

有 $N(\le 2000)$ 个农民, 他们住在 $N$ 个不同的村子里. 这 $N$ 个村子形成一棵树。每个农民初始时获得 $X$ 的钱。每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民。

对于每个农民给定一个值 $v_i$, 求：最少需要多少次操作, 使得每个农民最终拿到的钱 $\geq$ 给定的值。

题解

有个结论：每条边最多进行一次操作。

用 $f[x][i]$ 表示以 $x$ 为根的子树内部进行 $i$ 次操作，根节点最多能给出多少钱。如果为负数则表示需要多少钱。

背包转移。对于 $x$ 的子节点 $y$ ，可以对 $(x,y)$ 这条边进行操作；如果以 $y$ 为根的子树能自给自足（$f[y][j]\geq 0$），那么可以不对 $(x,y)$ 进行操作，直接转移到 $x$ 。方程式为：

$$\begin{cases} f[x][i]+f[y][j]\rightarrow f[x][i+j+1] \\ f[x][i]\rightarrow f[x][i+j] \ (f[y][j]\geq 0)\end{cases}$$

最后找到第一个使得 $f[1][i]\geq 0$ 的 $i$ 即为答案。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=2005;
struct Edge {
    int next,to;
} edge[N<<1];
int n,m,a,b,cnt,head[N],v[N],siz[N],f[N][N];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    siz[x]=1;
    memset(f[x],~0x3f,sizeof(f[x]));
    f[x][0]=f[x][1]=m-v[x];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        dfs(y,x);
        static int g[N]; memset(g,~0x3f,sizeof(g));
        for (int j=0;j<siz[x];j++) for (int k=0;k<siz[y];k++)
        {
            g[j+k+1]=max(g[j+k+1],f[x][j]+f[y][k]);
            if (f[y][k]>=0) g[j+k]=max(g[j+k],f[x][j]);
        }
        siz[x]+=siz[y];
        for (int i=0;i<=siz[x];i++) f[x][i]=g[i];
    }
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) v[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    return !printf("%d",lower_bound(f[1],f[1]+n,0)-f[1]);
}