题解 P4016 【负载平衡问题】

作为一道网络流24题，当然是用网络流，而显然是用最小费用最大流，那么问题就在如何建图了。。。建完了就上裸的EK就可以了。。 那么，要使所有的仓库货物都一样显然，货物数量大于平均值的要运出，小于平均值的就运入。对于大于平均值的，我们就和s连边，小于的就和t连边（当然反过来是一样的）。流量就是货物数量和平均值的差，也就是还需要运出或运入多少。费用为0，因为s和t本来就是超级源和超级汇，是新加的，我们只是借来表示一下关系而已，并不需要花费。 当然，对于相邻的点我们也需要建边，建的边流量为inf，因为可以随便运多少，费用就是1了。 #### 注意，图为无向图，正着反着都要建边。 那为什么要这么建图哪？显然，大于平均值的点流向小于平均值的点，不正是往小于平均值的点运货物么，每一条选入最大流的边u->v就是u往v运货物 ## 代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int inf=100000000; double avr=0; int n,s,t,cnt=-1; int a[100100]; int head[100100],nxt[100100],to[100100],val[100100],w[100100]; int del[100100],q[100100],dis[100100],f[100100],pre[100100]; void addedge(int x,int y,int z,int k) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; w[cnt]=z; val[cnt]=k; } bool spfa() { memset(f,0,sizeof(f)); memset(dis,-1,sizeof(dis)); q[1]=s,dis[s]=0,f[s]=1,del[s]=0x7fffffff; int l=0,r=1; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if((dis[v]>dis[u]+val[i] || dis[v]==-1) && w[i]) { dis[v]=dis[u]+val[i]; del[v]=min(del[u],w[i]),pre[v]=i; if(!f[v]) { f[v]=1; q[++r]=v; } } } f[u]=0; } return dis[t]!=-1; } int main() { memset(head,-1,sizeof(head)); scanf("%d",&n); s=0,t=n+1; for(int i=1;i<=n;i++) scanf("%d",&a[i]),avr+=a[i]; avr/=n; for(int i=1;i<=n;i++) { if(a[i]>avr)addedge(s,i,a[i]-avr,0),addedge(i,s,0,0); else addedge(i,t,avr-a[i],0),addedge(t,i,0,0);//和s，t连边 int j=i+1,k=i-1; if(i==n) j=1; if(i==1) k=n; addedge(i,j,inf,1),addedge(j,i,0,-1); addedge(i,k,inf,1),addedge(k,i,0,-1);//和相邻的点连边 } int res=0; while(spfa())//EK { res+=dis[t]*del[t]; int tmp=t; while(tmp!=s) { w[pre[tmp]]-=del[t]; w[pre[tmp]^1]+=del[t]; tmp=to[pre[tmp]^1]; } } printf("%d",res); return 0; } ```