poj 2516 最小费用最大流（从不同仓库运送不同货物给不同客户）

题意：有N个客户，M个仓库，和K种货物。已知每个客户需要每种货物的数量（N*M），每个仓库存储每种货物的数量（M*K），每个仓库运输各种货物去各个客户的单位费用（K个矩阵，每个矩阵大小为N*M）。判断所有的仓库能否满足所有客户的需求，如果可以，求出最少的运输总费用。

思路：最小费用最大流。对每一种货物分别建图，节点为仓库和客户，再加上一个超级源点和超级汇点。用最小费用最大流判断是否有能够满足所有客户的方案，如果有，求出完成这种货物运输的最小费用；如果没有，那么将标志变量flag置0，读入之后的数据输出-1即可。如果所有的货物都有方案能够满足客户，则将所有通过最小费用最大流求出的总费用相加输出即可。

#include <stdio.h>
#include <string.h>
#include <math.h>
#define min(a,b) a<b?a:b
#define INF 0x3fffffff
#define N 105
int need[N/2][N/2],supply[N/2][N/2],cost[N/2][N/2];//数组内容顾名思义
struct edge{
	int y,cost,cap,next;
}e[N*N];
int dis[N],visited[N],first[N],index[N],pre[N],q[200000];
int n,m,k,t,sum,res1,res2=0,top;//res1是每次最小费用最大流求出的值，res2是全局最小值
void add(int x,int y,int cost,int cap){
	e[top].y = y;
	e[top].cost = cost;
	e[top].cap = cap;
	e[top].next = first[x];
	first[x] = top++;
	e[top].y = x;
	e[top].cost = -cost;
	e[top].cap = 0;
	e[top].next = first[y];
	first[y] = top++;
}
void init(){
	res1 = top = sum = 0;
	memset(first,-1,sizeof(first));
}
int spfa(){
	int front,rear,i,now;
	for(i = 0;i<=t;i++)
		dis[i] = INF;
	front = rear = -1;
	q[++rear] = 0;
	dis[0] = 0;
	memset(visited,0,sizeof(visited));
	memset(pre,-1,sizeof(pre));
	while(front < rear){
		now = q[++front];
		visited[now] = 0;
		for(i = first[now];i!=-1;i=e[i].next)
			if(e[i].cap && dis[e[i].y]>dis[now]+e[i].cost){
				dis[e[i].y] = dis[now] + e[i].cost;
				if(!visited[e[i].y]){
					visited[e[i].y] = 1;
					q[++rear] = e[i].y;
				}
				pre[e[i].y] = now;
				index[e[i].y] = i;
			}
	}
	if(dis[t] == INF)
		return 0;
	return 1;
}
void update(){
	int i,aug = INF;
	for(i = t;i!=0;i=pre[i])
		aug = min(aug,e[index[i]].cap);
	res1 += aug * dis[t];
	for(i = t;i!=0;i=pre[i]){
		e[index[i]].cap -= aug;
		e[index[i]^1].cap += aug;
	}
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%d %d %d",&n,&m,&k)&&(n+m+k)){
		int i,j,g,flag = 1;
		res2 = 0;
		for(i = 1;i<=n;i++)
			for(j = 1;j<=k;j++)
				scanf("%d",&need[i][j]);
		for(i = 1;i<=m;i++)
			for(j = 1;j<=k;j++)
				scanf("%d",&supply[i][j]);
		for(g = 1;g<=k;g++){//对于每种货物，分别建图调用最小费用最大流
			for(i = 1;i<=n;i++)
				for(j = 1;j<=m;j++)
					scanf("%d",&cost[i][j]);
			if(flag){	
				init();	
				
				for(j = 0,i = 1;i<=m;i++)//仓库提供此种货物的总量
					j += supply[i][g];
				for(i = 1;i<=n;i++)//客户需要此种货物的总量
					sum+=need[i][g];
				if(j<sum){//如果供不应求
					flag = 0;
					continue;
				}

				for(i = 1;i<=m;i++)
					if(supply[i][g])//不提供货物的仓库不必加边进去
						for(j = 1;j<=n;j++)
							add(i,j+m,cost[j][i],supply[i][g]);//仓库到客户的边
				for(i = 1;i<=m;i++)
					add(0,i,0,supply[i][g]);//超级源点到仓库的边
				for(i = m+1;i<=m+n;i++)
					add(i,m+n+1,0,need[i-m][g]);//客户到超级汇点的边
				t = m+n+1;
				while(spfa())
					update();
				res2 += res1; 
			}
		}
		if(flag)
			printf("%d\n",res2);
		else
			printf("-1\n");
	}
	return 0;
}

for(i = first[t],j=0;i!=-1;i=e[i].next)//计算总流量，用来判断是否满流
	j += e[i].cap;