【GDKOI2014】JZOJ2020年8月13日提高组T2 石油储备计划

题目

Description

Input

Output

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

Sample Input

2

3

6 1 5

1 2 1

2 3 2

5

4 5 4 3 2

1 3 1

1 2 2

2 4 3

2 5 4

Sample Output

4

4

Data Constraint

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

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

Hint

对于第一组数据，从城市1到城市2运输2桶石油，代价为\(1*2=2\)；从城市3往城市2运输1桶石油，代价为\(2*1=2\)。此时三个城市储备量都为4桶，该状态的平衡度为0。

对于第二组数据，从城市2到城市5运输1桶石油，代价为\(1*4=4\)；此时五个城市储备量为(4,4,4,3,3)，该状态的非平衡度为1.2，是能达到的所有状态的最小值。

题解

题意

给出一棵树，有边权

定义一个非平衡度（如题）

问如何运输使得非平衡度最小，且代价最低

分析

很容易发现非平衡度最小有两种情况

当\(sum\%n=0\)，答案为\(\dfrac{sum}{n}\)
若不为0，答案为\(\left \lfloor\dfrac{sum}n{}\right \rfloor\)或\(\left \lfloor\dfrac{sum}n{}\right \rfloor+1\)

那么容易想到最小费用最大流

所有点往源点连一条流量为油桶数量，费用为0的边
所有点往汇点连一条流量为\(\left \lfloor\dfrac{sum}n{}\right \rfloor\)，费用为0的边
对于读入的点，连流量正无穷，费用读入的边（注意是双向，加上反向弧总共4条）

然后跑一遍最小费用最大流

随后把所有连向汇点的边流量加一

再跑一遍

两次答案之和即为答案

Code

#include<bits/stdc++.h>

#define rg register

#define inf 999999999999

using namespace std;

struct node

{

    long long to,next,val,flow;

}a[5005];

long long t,n,x,y,z,S,T,ans,ans1,tot,sum,head[5005],bj[5005],dis[5005],sy[5005];

inline void add(long long x,long long y,long long z,long long v)

{

    a[tot].to=y;

    a[tot].flow=z;

    a[tot].val=v;

    a[tot].next=head[x];

    head[x]=tot;

    ++tot;

}

inline long long OK()

{

    long long plus=inf;

    for (rg long long i=0;i<=n+2;++i)

        if (bj[i])

            for (rg long long j=head[i];j!=-1;j=a[j].next)

                if (!bj[a[j].to]&&a[j].flow) plus=min(plus,dis[a[j].to]+a[j].val-dis[i]);

    if (plus==inf) return 0;

    for (rg long long i=0;i<=n+2;++i)

    {

        if (bj[i])

        {

            bj[i]=0;

            dis[i]+=plus;

        }

    }

    return 1;

}

inline long long wwl(long long now,long long ss)

{

    if (now==T)

    {

        ans1+=dis[S]*ss;

        return ss;

    }

    bj[now]=1;

    long long u,x;

    for (rg long long i=head[now];i!=-1;i=a[i].next)

    {

        u=a[i].to;

        if (!bj[u]&&dis[u]+a[i].val==dis[now]&&a[i].flow)

        {

            x=wwl(u,min(ss,a[i].flow));

            if (x)

            {

                a[i].flow-=x;

                a[i^1].flow+=x;

                return x;

            }

        }

    }

    return 0;

}

inline void ffl()

{

    long long q;

    while (OK())

    {

        q=wwl(S,inf);

        while (q)

        {

            memset(bj,0,sizeof(bj));

            q=wwl(S,inf);

        }

    }

}

int main()

{

    freopen("test.in","r",stdin);

    freopen("test.out","w",stdout);

    scanf("%lld",&t);

    while (t--)

    {

        memset(head,-1,sizeof(head));

        memset(a,0,sizeof(a));

        memset(dis,0,sizeof(dis));

        memset(bj,0,sizeof(bj));

        scanf("%lld",&n);

        S=n+1;

        T=n+2;

        ans=sum=ans1=0;

        tot=0;

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

        {

            scanf("%lld",&x);

            add(S,i,x,0);

            add(i,S,0,0);

            sum+=x;

        }

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

        {

            scanf("%lld%lld%lld",&x,&y,&z);

            add(x,y,inf,z);

            add(y,x,0,-z);

            add(y,x,inf,z);

            add(x,y,0,-z);

        }

        sum/=n;

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

        {

            add(i,T,sum,0);

            add(T,i,0,0);

        }

        bj[S]=1;

        ffl();

        for (rg long long i=2;i<=tot;++i)

            if (a[i].to==T)

                a[i].flow++;

        bj[S]=1;

        ffl();

        printf("%lld\n",ans1);

    }

    return 0;

}

巴特西

【GDKOI2014】JZOJ2020年8月13日提高组T2 石油储备计划

【GDKOI2014】JZOJ2020年8月13日提高组T2 石油储备计划

题目

Description

Input

Output

Sample Input

Sample Output

Data Constraint

Hint

题解

题意

分析

Code

最新文章

热门文章