http://poj.org/problem?id=2516

题目中有k种货物，将k种货物分开求，最后再相加。引入1个超级源点和超级汇点，源点到每个仓库的容量为每个仓库的容量，费用为0.仓库到每个人的容量无穷，费用为输入的。人到仓库容量为0,费用为输入值的负值。人到汇点容量为每个人的购买力，费用为0.

#include <stdio.h>
#include <string.h>
#define MAXN 52
#define MAXM 104
#define INF 0x7f7f7f7f
#define MIN( x, y ) x > y ? y : x

int n, m, k;
int r[MAXN][MAXN]; //shopkeeper's order
int s[MAXN][MAXN]; //each supply place's storage
int mat[MAXN][MAXN]; //each kind goods's cost
int flow[MAXM][MAXM], c[MAXM][MAXM]; //flow and capacity
int cost[MAXM][MAXM];
int flag, pre[MAXM], dis[MAXM], mf[MAXM];

void ConstructMap( int p, int t )
{
	int i, j;
	memset( c, 0, sizeof( c ) );
	memset( cost, 0, sizeof( cost ) );
	for ( i = 1; i <= m; ++i )
		c[0][i] = s[i][p];
	for ( i = 1; i <= m; ++i )
		for ( j = 1; j <= n; ++j )
		{
			c[i][j+m] = INF;
			cost[i][j+m] = mat[j][i];
			cost[j+m][i] = -mat[j][i];
		}
	for ( i = 1; i <= n; ++i )
		c[i+m][t] = r[i][p];
}

int spfa( int n, int s, int t )
{
	int queue[110], visit[110];
	int top, tail, u, i, v;
	memset( dis, 0x7f, sizeof( dis ) );
	memset( visit, 0, sizeof( visit ) );
	memset( pre, -1, sizeof( pre ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	mf[s] = INF;
	while ( top != tail )
	{
		u = queue[top]; visit[u] = 0;
		top++;
		if ( top == n ) top = 0;
		for ( v = 0; v < n; ++v )
		if ( c[u][v] > flow[u][v] && dis[v] - cost[u][v] > dis[u] )
		{
			dis[v] = dis[u] + cost[u][v];
			mf[v] = MIN( mf[u], c[u][v]-flow[u][v] );
			pre[v] = u;
			if ( !visit[v] )
			{
				queue[tail] = v; visit[v] = 1;
				tail++;
				if ( tail == n ) tail = 0;
			}
		}
	}
	if ( pre[t] < 0 ) return 0;
	return 1;
}

int Min_Cost_Max_Flow( int n, int s, int t )
{
	int i, j, u, v, ans = 0;
	memset( flow, 0, sizeof( flow ) );
	while ( spfa( n, s, t ) )
 	{
		for ( u = pre[v=t]; v != 0; v = u, u = pre[v] )
		{
			flow[u][v] += mf[t];
			flow[v][u] -= mf[t];
		}
        ans += mf[t] * dis[t];
    }
	return ans;
}

int main()
{
	int i, j, p, sum, s1, s2;

	while ( 1 )
	{
		scanf( "%d%d%d", &n, &m, &k );
		if ( !n && !m && !k ) break;
		for ( i = 1; i <= n; ++i )
			for ( j = 1; j <= k; ++j )
				scanf( "%d", &r[i][j] );
		for ( i = 1; i <= m; ++i )
			for ( j = 1; j <= k; ++j )
				scanf( "%d", &s[i][j] );
		sum = 0; flag = 1;
		for ( j = 1; j <= k; ++j )
		{
			s1 = s2 = 0;
			for ( i = 1; i <= n; ++i )
				s1 += r[i][j];
			for ( i = 1; i <= m; ++i )
				s2 += s[i][j];
			if ( s1 > s2 )
			{
				flag = 0; break;
			}
		}
		for ( p = 1; p <= k; ++p )
		{
			for ( i = 1; i <= n; ++i )
				for ( j = 1; j <= m; ++j )
					scanf( "%d", &mat[i][j] );
			if ( !flag ) continue;
			ConstructMap( p, n+m+1 );
			sum += Min_Cost_Max_Flow( n+m+2, 0, n+m+1 );
		}
		printf( "%d\n", ( flag ? sum : -1 ) );
	}
	return 0;
}