GDKOI2014 石油儲備計劃

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


樣例解釋：


對于第一組數據，從城市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，是能達到的所有狀態的最小值。

Data Constraint

對于20%的數據，N<=15

對于100%的數據，T<=10，N<=100，0<=si<=10000，1<=X,Y<=N，1<=Z<=10000。

首先容易得到結論：達到平衡狀態時，每個點的油量要么為(sum/n)，要么為(sum/n)+1，現在每個點有一個初始容量，在樹上相鄰的點可以轉移石油。

我們可以據此建模

對于s向每個點，連一條上下界均為初始量的邊，費用為0，表示最初容量，

對于每個點向t，連一條下界為(sum/n)，上界為(sum/n)+1的邊，表示經轉移后的容量

對于原樹上相鄰的點，連一條下界為0，上界為正無窮，費用為距離的邊，表示轉移可用的路徑

然后跑一遍最小費用可行流即可

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>using namespace std;
typedef long long ll;int g[2001],next[2011],y[2011],cost[2011],flow[2011];
int que[2000011],dis[2011],lb[2011],mn[2011],vis[2011];
int du[2011],a[2011];
int tt,tl,n,i,s,t,S,T,x,z,q,sum,dt,tj;
ll ans;void star(int i,int j,int k,int l)
{tt++;next[tt]=g[i];g[i]=tt;y[tt]=j;flow[tt]=k;cost[tt]=l;tt++;next[tt]=g[j];g[j]=tt;y[tt]=i;flow[tt]=0;cost[tt]=-l;
}void Spfa()//記錄dis(最短路),min(最小流量),lb(連過的邊，退流用)
{int l,r,x,j,k;memset(dis,127,sizeof(dis));memset(mn,0,sizeof(mn));memset(lb,0,sizeof(lb));tl++;l=r=1;que[l]=S;dis[S]=0;mn[S]=21474836;vis[S]=tl;while(l<=r){x=que[l];j=g[x];while(j!=0){if(flow[j]>0){k=y[j];if(dis[x]+cost[j]<dis[k]){dis[k]=dis[x]+cost[j];if(mn[x]<flow[j])mn[k]=mn[x];else mn[k]=flow[j];lb[k]=j;if(vis[k]!=tl){r++;que[r]=k;vis[k]=tl;}}}j=next[j];}l++;vis[x]--;}
}void Minflow()
{int x,j;ans=0;while(true){Spfa();if(dis[T]==2139062143)break;ans+=(ll)mn[T]*dis[T];x=T;while(x!=S){j=lb[x];flow[j]-=mn[T];flow[j^1]+=mn[T];x=y[j^1];}}
}int main()
{scanf("%d",&dt);for(tj=1;tj<=dt;tj++){tt=1;memset(g,0,sizeof(g));memset(du,0,sizeof(du));scanf("%d",&n);sum=0;s=n+1;t=n+2;S=n+3;T=n+4;for(i=1;i<=n;i++){scanf("%d",&a[i]);du[i]+=a[i];du[s]-=a[i];sum+=a[i];}for(i=1;i<=n;i++){du[i]-=(sum/n);du[t]+=(sum/n);star(i,t,1,0);}for(i=1;i<n;i++){scanf("%d%d%d",&x,&z,&q);star(x,z,21474836,q);star(z,x,21474836,q);}star(t,s,21474836,0);for(i=1;i<=t;i++){if(du[i]>0)star(S,i,du[i],0);else star(i,T,-du[i],0);}Minflow();printf("%lld\n",ans);}
}

?