负载平衡问题（费用流）

负载平衡问题

https://www.luogu.org/problemnew/show/P4016

题目描述

输入输出格式

输入格式：

文件的第

第

输出格式：

输出最少搬运量。

输入输出样例

输入样例#1：

5
17 9 14 16 4

输出样例#1：

说明

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 const int INF=0x3f3f3f3f;
  8 const int N=50005;
  9 const int M=500005;
 10 int top;
 11 int dist[N],pre[N];
 12 bool vis[N];
 13 int c[N];
 14 int maxflow;
 15 
 16 struct Vertex{
 17     int first;
 18 }V[N];
 19 struct Edge{
 20     int v,next;
 21     int cap,flow,cost;
 22 }E[M];
 23 
 24 void init(){
 25     memset(V,-1,sizeof(V));
 26     top=0;
 27     maxflow=0;
 28 }
 29 
 30 void add_edge(int u,int v,int c,int cost){
 31     E[top].v=v;
 32     E[top].cap=c;
 33     E[top].flow=0;
 34     E[top].cost=cost;
 35     E[top].next=V[u].first;
 36     V[u].first=top++;
 37 }
 38 
 39 void add(int u,int v,int c,int cost){
 40     add_edge(u,v,c,cost);
 41     add_edge(v,u,0,-cost);
 42 }
 43 
 44 bool SPFA(int s,int t,int n){
 45     int i,u,v;
 46     queue<int>qu;
 47     memset(vis,false,sizeof(vis));
 48     memset(c,0,sizeof(c));
 49     memset(pre,-1,sizeof(pre));
 50     for(i=1;i<=n;i++){
 51         dist[i]=INF;
 52     }
 53     vis[s]=true;
 54     c[s]++;
 55     dist[s]=0;
 56     qu.push(s);
 57     while(!qu.empty()){
 58         u=qu.front();
 59         qu.pop();
 60         vis[u]=false;
 61         for(i=V[u].first;~i;i=E[i].next){
 62             v=E[i].v;
 63             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
 64                 dist[v]=dist[u]+E[i].cost;
 65                 pre[v]=i;
 66                 if(!vis[v]){
 67                     c[v]++;
 68                     qu.push(v);
 69                     vis[v]=true;
 70                     if(c[v]>n){
 71                         return false;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dist[t]==INF){
 78         return false;
 79     }
 80     return true;
 81 }
 82 
 83 int MCMF(int s,int t,int n){
 84     int d;
 85     int i,mincost;
 86     mincost=0;
 87     while(SPFA(s,t,n)){
 88         d=INF;
 89         for(i=pre[t];~i;i=pre[E[i^1].v]){
 90             d=min(d,E[i].cap-E[i].flow);
 91         }
 92         maxflow+=d;
 93         for(i=pre[t];~i;i=pre[E[i^1].v]){
 94             E[i].flow+=d;
 95             E[i^1].flow-=d;
 96         }
 97         mincost+=dist[t]*d;//dist[t]为单位最小费用，d为总量
 98     }
 99     return mincost;
100 }
101 
102 int aa[105];
103 
104 int main(){
105     int n,m;
106     int v,u,w,c;
107     int s,t;
108     cin>>n;
109     init();
110     int sum=0;
111     for(int i=1;i<=n;i++){
112         cin>>aa[i];
113         sum+=aa[i];
114     }
115     sum/=n;
116     for(int i=1;i<=n;i++){
117         aa[i]=sum-aa[i];
118     }
119     s=0,t=n+1;
120     for(int i=1;i<=n;i++){
121         if(aa[i]>0){
122             add(s,i,aa[i],0);
123         }
124         else if(aa[i]<0){
125             add(i,t,-aa[i],0);
126         }
127     }
128     for(int i=2;i<n;i++){
129         add(i,i-1,INF,1);
130         add(i,i+1,INF,1);
131     }
132     add(1,n,INF,1);
133     add(1,2,INF,1);
134     add(n,1,INF,1);
135     add(n,n-1,INF,1);
136     int ans=MCMF(s,t,n+2);
137     cout<<ans<<endl;
138 }

View Code