学步园

题意：有N个客户，M个仓库，和K种货物。已知每个客户需要每种货物的数量，每个仓库存储每种货物的数量，每个仓库运输各种货物去各个客户的单位费用。判断所有的仓库能否满足所有客户的需求，如果可以，求出最少的运输总费用。
题解：因为 K 种产品互相不干扰，所以关键是把 K 种产品分开求解。

#include <queue>
#include <iostream>
using namespace std;

#define N 155
#define INF 999999

int need[N][N], store[N][N], cost[N][N][N];
int cap[N][N], flow[N][N], fee[N][N];
int pre[N], dis[N], vis[N];
int n, m, kind, s, t;

void spfa()
{
	queue<int> que;
	memset(vis,0,sizeof(vis));
	memset(pre,-1,sizeof(pre));

	for ( int i = 0; i <= t; i++ )
		dis[i] = INF;
	dis[s] = 0;
	vis[s] = 1;
	que.push(s);

	while ( ! que.empty() )
	{
		int u = que.front();
		que.pop();
		vis[u] = 0;
		for ( int v = 0; v <= t; v++ )
		{
			if ( cap[u][v] > flow[u][v] && dis[v] > dis[u] + fee[u][v] )
			{
				dis[v] = dis[u] + fee[u][v];
				pre[v] = u;
				if ( ! vis[v] )
				{
				    que.push(v);
				    vis[v] = 1;
				}
			}
		}
	}
}

void mcmf ()
{
	while ( 1 )
	{
		spfa(); 
		if ( pre[t] == -1 )
			return;

		int tt = t;
		int minflow = INF;

		while ( pre[tt] != -1 )
		{
			if ( minflow > cap[pre[tt]][tt] - flow[pre[tt]][tt] )
				minflow = cap[pre[tt]][tt] - flow[pre[tt]][tt];
			tt = pre[tt];
		}
	
		tt = t;
		while ( pre[tt] != -1 )
		{
			flow[pre[tt]][tt] += minflow;
			flow[tt][pre[tt]] -= minflow;
			tt = pre[tt];
		}
	}
}

void solve()
{
	int i, j, k, res = 0;
	for ( k = 1; k <= kind; k++ )
	{		
		memset(cap,0,sizeof(cap));
		memset(fee,0,sizeof(fee));
		memset(flow,0,sizeof(flow));

		for ( i = 1; i <= m; i++ )
			cap[s][i] = store[i][k];

		for ( i = 1; i <= m; i++ )
			for ( j = 1; j <= n; j++ )
				cap[i][j+m] = store[i][k];

		for ( i = 1; i <= n; i++ )
			cap[i+m][t] = need[i][k];
				
		for ( i = 1; i <= m; i++ )
			for ( j = 1; j <= n; j++ )
			{
				fee[i][j+m] = cost[k][j][i]; // 注意是cost[k][j][i]。这地方调了一个多小时！！！
				fee[j+m][i] = -fee[i][j+m];
			}

		mcmf();

		for ( i = 1; i <= m; i++ )
			for ( j = 1; j <= n; j++ )
				res += flow[i][j+m] * fee[i][j+m];
	}
	printf("%d\n",res);
}

int main()
{
	while ( scanf("%d%d%d",&n,&m,&kind) )
	{
		s = 0; 
		t = m + n + 1;
		
		if ( !n && !m && !kind ) break;

		int i, j, k;
		for ( i = 1; i <= n; i++ )
			for ( j = 1; j <= kind; j++ )
				scanf("%d",&need[i][j]);

		for ( i = 1; i <= m; i++ )
			for ( j = 1; j <= kind; j++ )
				scanf("%d",&store[i][j]);

		for ( k = 1; k <= kind; k++ )
			for ( i = 1; i <= n; i++ )
				for ( j = 1; j <= m; j++ )
					scanf("%d",&cost[k][i][j]);

		for ( k = 1; k <= kind; k++ )
		{
			int totalNeed = 0;
			int totalStore = 0;

			for ( i = 1; i <= n; i++ )
				totalNeed += need[i][k];

			for ( i = 1; i <= m; i++ )
				totalStore += store[i][k];

			if ( totalStore < totalNeed )
			{
				printf("-1\n");
				goto next;
			}
		}

		solve();
next:;
	}
	return 0;
}