題意：有M個貨物供應點，它提供k種貨物，有N個商店，這N個商店分別要從貨物點訂購一定量的這k種物品，每個供應點對這k種貨物的供應量不同，每個商店對k種物品的需求量也不同，每個貨物供應點向每個商店送不同種貨物的單個物品的花費不同，現在給出貨物供應點、商店、k種貨物、花費間的關系，現在讓你針對商店給出的訂單，讓你決定如何使所有供應點完成訂單任務的最小花費，若能完成任務，則輸出最小花費，否則輸出-1.
為我的英語拙計啊。。。到網上找了翻譯才看懂。。太水了。
第一次寫費用流，參考了別人的代碼，寫了點注釋，算是費用流第一A。紀念一下。。
貼代碼
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 105
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
using namespace std;
int c[Max][Max]; //流量限制
int f[Max][Max];//最大流
int dis[Max];
int w[Max][Max];//費用
bool visit[Max];
int path[Max];
int S,T;
int q[Max*100];
int spfa()//最短路
{
int i,j;
for(i=0; i<=T; i++)
dis[i]=inf,path[i]=-1,visit[i]=0;
dis[S]=0;
visit[S]=1;
int num=0,cnt=0;
q[num++]=S;
while(num>cnt)
{
int temp=q[cnt++];
visit[temp]=0;
for(i=1; i<=T; i++)
if(c[temp][i]>f[temp][i]&&dis[temp]+w[temp][i]<dis[i])
{
path[i]=temp;
dis[i]=dis[temp]+w[temp][i];
if(!visit[i])
{
visit[i]=1;
q[num++]=i;
}
}
}
if(path[T]==-1)
return 0;
return 1;
}
void getMaxflow()//找增廣路並調整流量
{
while(spfa())
{
int maxFlow=inf;
int pre=T;
while(path[pre]!=-1)
{
maxFlow=min(maxFlow,c[path[pre]][pre]-f[path[pre]][pre]);
pre=path[pre];
}
pre=T;
while(path[pre]!=-1)//調整流量
{
f[path[pre]][pre]+=maxFlow;
f[pre][path[pre]]=-f[path[pre]][pre];
pre=path[pre];
}
}
}
int need[Max][Max],have[Max][Max];
int cost[Max][Max][Max];
int main()
{
int i,j,k,l,n,m,d;
while(scanf("%d%d%d",&n,&m,&k),(n+m+k))
{
for(i=1; i<=n; i++) //客人i
for(j=1; j<=k; j++) //需要貨物j的數量
scanf("%d",&need[i][j]);
for(i=1; i<=m; i++) //倉庫i
for(j=1; j<=k; j++) //有貨物j的數量
scanf("%d",&have[i][j]);
for(i=1; i<=k; i++) //第i個商品
for(j=1; j<=n; j++) //送到j地點
for(d=1; d<=m; d++) //從d地點的
scanf("%d",&cost[i][d][j]);//的費用
S=0,T=n+m+1;//超級源點0，超級匯點n+m+1;
//cout<<1<<endl;
bool flag=0;
int ans=0;
for(i=1; i<=k; i++)
{
memset(c,0,sizeof(c));
memset(f,0,sizeof(f));
memset(w,0,sizeof(w));
for(j=1; j<=m; j++)//源點到每個倉庫的容量為該倉庫這種物品的存量
c[0][j]=have[j][i];
for(j=1; j<=n; j++)//每個客人到匯點的容量為該客人對物品的需求量
c[m+j][T]=need[j][i];
for(j=1; j<=m; j++)
for(d=1; d<=n; d++)
c[j][d+m]=have[j][i];//每個倉庫到每個客人之間的容量為該倉庫這種物品的存量
for(j=1; j<=m; j++)
for(d=1; d<=n; d++)
w[j][d+m]=cost[i][j][d],w[d+m][j]=-w[j][d+m];//花費，負花費用於回流
getMaxflow();
//cout<<1<<endl;
for(j=1; j<=n; j++)
if(c[j+m][T]!=f[j+m][T])//如果不能供貨，則輸出-1
{
flag=1;
break;
}
if(flag)
break;
for(j=1; j<=m; j++)
for(d=1; d<=n; d++)
ans+=f[j][d+m]*w[j][d+m];//總費用
// cout<<1<<endl;
}
if(flag)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
return 0;
}
