題目意思，這個理解起來就很費勁
有N個供給商，M個雇主，K種物品。每個供給商對每種物品的的供給量已知，每個雇主對每種物品的需求量的已知，從不同的供給商輸送不同的貨物到不同的雇主手上需要不同的花費，又已知從供給商Mj送第kind種貨物的單位數量到雇主Ni手上所需的單位花費。
問：供給是否滿足需求？若是滿足，最小運費是多少？
樣例解釋
算法分析
1、供給是否滿足需求
首先我們要看供給是否滿足需求，要求最小費用，必須先滿足供給大於等於需求才可以。我們必須求出第k種貨物的總供給量和總消費量。如果有一種貨物的消費量大於供給量，那麼直接輸出-1，不過記住要先將題目的輸入讀完，否則wa到死。然後只有供給大於需求，才能找出最小值，也一定能找到最小值。
2、 最小費用最大流
從題目明顯看出由於是n個人，所以死多源點多匯點的最小費用最大流。但是其實題目已經給出了提示，後面是k個N*M的矩陣，其實就是想讓我們先計算每一種貨物的最小費用，然後求和即可。通過分析很容易發現，這k中貨物的最小費用好不想干，不會相互影響。
3、 那麼如何建圖呢
源點s和匯點t，定義各點編號如下：源點s編號為0，供給商編號從1到M，雇主編號從M+1到M+N，匯點t編號為M+N+1。總結點數nmax=M+N+2，申請每條邊的“花費”空間map[nMax][ nMax]和“容量”空間cap[nMax][ nMax]，並初始化為全0。源點s向所有供給商M建邊，費用為0，容量為供給商j的供給量。
每個供給商都向每個雇主建邊，正向弧費用為輸入數據的第k個矩陣，容量為供給商j的供給量；反向弧費用為正向弧費用的負數，容量為0。
所有雇主向匯點t建邊，費用為0，容量為雇主i的需求量。
4、算法實現
對於第k種物品的圖，用spfa算法求解最小費用路徑（增廣流鏈），在這條路徑上求出流量的最小值，其實也是最大的流量，然後在路徑上正向減去此流量，反向加上此流量，費用為單價乘以此流量。
代碼：
[cpp]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define nMax 300
#define inf 0x7fffffff
#define Min(a,b) (a<b?a:b)
int map[nMax][nMax];//map[i][j]表示對於每種k物品從i運輸到j所花費的錢
int vis[nMax];//表示i是否用過
int cap[nMax][nMax];//表示i到j的最大通貨量
int dis[nMax];//到i的距離
int que[nMax];//隊列
int pre[nMax];//保存每一條最短增流路
int num,ans;//num-最後的匯點，ans最終的答案
int spfa()//spfa求最短路徑，dijstra不允許有負權，所以這裡使用spfa
{
int i,k;
int head,tail;
memset(vis, 0, sizeof(vis));
for (i = 0; i <= num; ++ i)
{
dis[i] = inf;
}
dis[0] = 0;
vis[0] = 1;
head = tail = 0;
que[0] = 0;
tail ++;
while (head < tail)
{
k = que[head];
vis[k] = 0;
for (i = 0; i <= num; ++ i)
{
if (cap[k][i] && dis[i] > dis[k] + map[k][i])//如果k到i還有量，表明還可以增流，那麼就求最短路
{
dis[i] = dis[k] + map[k][i];
pre[i] = k;
if (!vis[i])
{
vis[i] = 1;
que[tail ++] = i;
}
}
}
head ++;
}
if (dis[num] < inf)
{
return 1;
}
return 0;
}
void end()
{
int i, sum = inf;
for (i = num; i!= 0; i = pre[i])//找到可以增加的最大的流，是整條最短路上的最小流
{
sum = Min(sum, cap[pre[i]][i]);
}
for (i = num; i != 0; i = pre[i])
{
cap[pre[i]][i] -= sum;//正向減去增加的流
cap[i][pre[i]] += sum;//逆向加上增加的流
ans += map[pre[i]][i] * sum;//計算本次的花費，實際上就是從place pre[i]到第i個人對於當前種類的物品所花費的錢
}
}
int main()
{
int N,M,K,i,j,k;
int need[nMax][nMax];
int needk[nMax];
int have[nMax][nMax];
int havek[nMax];
int flag;
while (scanf("%d %d %d", &N, &M, &K), N)
{
memset(needk, 0, sizeof(needk));
for (i = 1; i <= N; ++ i)
{
for (j = 1; j <= K; ++ j)
{
scanf("%d", &need[i][j]);
needk[j] += need[i][j];//求出每種貨物最大的需求量
}
}
memset(havek, 0, sizeof(havek));
for (i = 1; i <= M; ++ i)
{
for (j = 1; j <= K; ++ j)
{
scanf("%d", &have[i][j]);
havek[j] += have[i][j];//計算出所有地方能提供出每種貨物的最大量
}
}
flag = 1;
for (i = 1; i <= K; ++ i)
{
if (needk[i] > havek[i])//如果有物品供給不足，那麼肯定不能完成運送
{
flag = 0;
break;
}
}
ans = 0;
num = N + M + 1;
for (k = 1; k <= K; ++ k)//計算每種貨物的最小花費，然後求和
{
memset(cap, 0, sizeof(cap));
memset(map, 0, sizeof(map));
for (i = 1; i <= N; ++ i)
{
for (j = 1; j <= M; ++ j)
{
scanf("%d", &map[j][M + i]);//將N個人映射到M+1-M+N區間上，這樣方便建圖，map j到M+i就是從地方j運送到人i的花費
map[M + i][j] = -map[j][M + i];
cap[j][M + i] = have[j][k];//j到i的量是第k種貨物的在place j的最大的量
cap[M + i][j] = 0;
}
}
if (!flag)
{
continue;
}
for (i = 1; i <= M; ++ i)
{
cap[0][i] = have[i][k];//源點到place i其實也設為第k中貨物在place i的量
map[0][i] = map[i][0] = 0;//從原點到i花費為0
}
for (i = 1; i <= N; ++ i)
{
cap[M + i][num] = need[i][k];//從人i到匯點的量設為第i個人對第k種貨物的需求量。
map[M + i][num] = map[num][M + i] = 0;
}
while (spfa())//求第k種貨物的最小花費
{
end();
}
}
if (flag)
{
printf("%d\n", ans);
}
else
printf("-1\n");
}
return 0;
}
