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。
對于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);} }
?