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

【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;
}