Problem

Description

Input

Output

对于每组数据，输出一个整数，表示达到“平衡”状态所需的最小代价。

Data Constraint

对于20%的数据，N<=15

对于100%的数据，T<=10，N<=100，0<=si<=10000，1<=X,Y<=N，1<=Z<=10000。

Solution

这题可以用费用流求解，奈何太长了

只好DP了

我们发现，当达到所谓“平衡”状态时，每个点的石油数应是ave或ave+1

所以我们考虑枚举子树中ave+1的节点的个数

设\(f_{i,j}\)表示以i为根的子树中有j个ave+1的节点的最小贡献

如果我们暴力枚举会T飞

所以考虑合并

用\(g_{j}\)来存当前的当前的答案

则f数组存的则是之前做的所有的儿子的答案

则该儿子节点的贡献则为\(abs(sum_{son}-ave\times tree_{son}-k)\)

其中，sum为该子树原有的石油数，tree表示该子树的节点数，而k则为该子树中的ave+1的节点的个数

做完后再用g数组更新f

时间复杂度\(O(n^{3})\)

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int t,sum,n,i,a,b,c,dec,ave,len,go[1001],to[1001],last[101],jz[1001],tree[101],cnt[101],w[101];

long long f[101][1001],g[1001];

void make(int x,int y,int z)

{

    go[++len]=y;to[len]=last[x];jz[len]=z;last[x]=len;

}

void dp(int x,int fa)

{

	f[x][0]=f[x][1]=0;

    tree[x]=1;cnt[x]=w[x];

    for (int k=last[x];k;k=to[k])

    {

        if (go[k]==fa) continue;

        dp(go[k],x);

        tree[x]+=tree[go[k]];cnt[x]+=cnt[go[k]];

    }

    for (int k=last[x];k;k=to[k])

    {

    	memset(g,127,sizeof(g));

        if (go[k]==fa) continue;

        for (int j=0;j<=dec && j<=tree[x];j++)

        {

            for (int i=0;i<=j && i<=tree[go[k]];i++)

            {

                g[j]=min(g[j],f[x][j-i]+f[go[k]][i]+1ll*abs(cnt[go[k]]-tree[go[k]]*ave-i)*jz[k]);

            }

        }

        for (int j=0;j<=dec && j<=tree[x];j++)

            f[x][j]=g[j];

    }

}

int main()

{

    scanf("%d",&t);

    for (;t;t--)

    {

    	memset(last,0,sizeof(last));

        scanf("%d",&n);sum=0;

        for (i=1;i<=n;i++)

        {

            scanf("%d",&w[i]);

            sum+=w[i];

        }len=0;

        for (i=1;i<n;i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            make(a,b,c);

            make(b,a,c);

        }

        dec=sum%n;

        ave=sum/n;

        memset(f,127,sizeof(f));

        dp(1,0);

        printf("%lld\n",f[1][dec]);

    }

}

要恶补网络流啊

巴特西

jzoj 3567. 【GDKOI2014】石油储备计划