最小费用流问题 —— 负载平衡

Published on 2010 / 03 / 28

最小费用流问题，花了两个中午解决，顺便写成了函数。

直接将每个点i拆分成<i,a>,<i,b>，且之间连一条容量为无穷大，费用为0的边。我们将源点与<i,a>间连一条容量为a[i]，费用为0的边。将<i,b>与<j,a>间连一条容量为无穷大，费用为1的边(j为i旁边两点)。将<i,b>与汇点连一条容量为平均值，费用为0的边。最后的费用流即为答案。

问题描述：

G 公司有n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

编程任务：

对于给定的n 个环形排列的仓库的库存量，编程计算使n 个仓库的库存数量相同的最少搬运量。

数据输入：

由文件input.txt 提供输入数据。文件的第1 行中有1 个正整数n （n<=100），表示有n 个仓库。第2 行中有n 个正整数，表示n 个仓库的库存量。

结果输出：

程序运行结束时，将计算出的最少搬运量输出到文件output.txt 中。

样例：

input.txt
5
17 9 14 16 4

output.txt
11

我的代码

/*
Author ZHOU Cheng
Date 2010-3-24
Mincost flow
*/

#include<stdio.h>
#define Maxnum 1000000

int N,S,T,Ans,Add,Traffic[222][222],Cost[222][222],Value[222],Back[222],Now[222];
char Pan,Mark[222];

int Min(int a,int b)
{
 if(a>b) return b;
 else return a;
}

void Find(int point)
{
 if(point!=T)
 {
  Mark[point]=1;
  int a,b;
  for(a=1;a<=T;a++)
   if(Traffic[point][a]>0)
   {
    if(Now[a]==0)
     {Now[a]=Min(Now[point],Traffic[point][a]);Back[a]=point;Value[a]=Value[point]+Cost[point][a];Find(a);}
    else
    {
     if(Value[a]>Value[point]+Cost[point][a])
      {Now[a]=Min(Now[point],Traffic[point][a]);Back[a]=point;Value[a]=Value[point]+Cost[point][a];Find(a);}
     else if(Value[a]==Value[point]+Cost[point][a])
     {
      b=Min(Now[point],Traffic[point][a]);
      if(b>Now[a])
       {Now[a]=b;Back[a]=point;Find(a);}
     }
    }
   }
  Mark[point]=0;
 }
}

void Set(int point)
{
 if(point!=S)
 {
  int a,b;
  a=Back[point];b=point;
  Traffic[a][b]-=Add;
  Traffic[b][a]+=Add;
  Set(a);
 }
}

int main()
{
    freopen("Mincost flow.in","r",stdin);
    freopen("Mincost flow.out","w",stdout);
    // 读入数据
 scanf("%d",&N);
 int a,b,c,d;
 for(a=1,b=0;a<=N;a++)
 {
  scanf("%d",&c);
  b+=c;
  Traffic[0][a]=c;
 }
 // 初始化 源点 和 汇点 的流
 b/=N;S=0;T=2*N+1;
 for(a=1;a<=N;a++)
  Traffic[a+N][T]=b;
 for(a=1;a<=N;a++)
  Traffic[a][a+N]=Maxnum;
 // 对边赋权值
 for(a=1;a<=N;a++)
 {
  b=a-1;
  if(b<1) b=N;
  Traffic[a+N][b]=Maxnum;
  Cost[a+N][b]=1;
  Cost[b][a+N]=-1;
  b=a+1;
  if(b>N) b=1;
  Traffic[a+N][b]=Maxnum;
  Cost[a+N][b]=1;
  Cost[b][a+N]=-1;
 }
 // 最小费用流
 Pan=1;Ans=0;
 while(Pan)
 {
  memset(Value,0,sizeof(Value));
  memset(Back,0,sizeof(Back));
  memset(Now,0,sizeof(Now));
  for(a=1,Pan=0;a<=N;a++)
      if(Traffic[S][a]>0)
      {
    if(Now[a]==0)
     {Back[a]=S;Now[a]=Traffic[S][a];Value[a]=Value[S]+Cost[S][a];Find(a);}
    else
    {
     if(Value[a]>Value[S]+Cost[S][a])
      {Back[a]=S;Now[a]=Traffic[S][a];Value[a]=Value[S]+Cost[S][a];Find(a);}
     else if(Value[a]==Value[S]+Cost[S][a]&&Now[a]<Traffic[S][a])
      {Back[a]=S;Now[a]=Traffic[S][a];Value[a]=Value[S]+Cost[S][a];Find(a);}
    }
      }
  if(Now[T]!=0)
   {Pan=1;Add=Now[T];Set(T);Ans+=Add*Value[T];}
 }
 printf("%d\n",Ans);
 return 0;
}