這道題目分別求每一商品的最小費用，然後加起來就可以了。
但是調試了很久，郁悶，好多地方寫的不對。也許是自己沒看模版的原因。
記住：
1，反向邊初始化為0；
2，spfa的標記。
3，初始化。
[html]
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
int u;
int v;
int next;
bool friend operator < (node a, node b){
return a.u< b.u;
}
}edge[100001];
int head[1000010];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int n,m,k;
int need[101][101];//第i個店主對物品j的需求；
int give[101][101];//第i個供貨商對物品j的供貨能力；
int fei[101][101][101];//i,j,k;第k個物品，供貨商j對店主i的費用
int cost[501][501];
int p[1001];
int num=0;
void add(int l,int r,int v)
{
edge[num].u=r;
edge[num].v=v;
edge[num].next=head[l];
head[l]=num;
num++;
}
int spfa()
{
int visit[100001];
int i,dist[10001];
memset(visit,0,sizeof(visit));
memset(p,-1,sizeof(p));
queue<int>q;
for(i=0;i<=n+m+1;i++)dist[i]=INF;
dist[0]=0;
q.push(0);
visit[0]=1;
while(!q.empty())
{
int e;
e=q.front();
q.pop();
visit[e]=0;
//printf("tan->%d\n",e);
for(i=head[e];i!=-1;i=edge[i].next)
{
int r=edge[i].u;
// printf("%d %d %d %d %d\n",e,r,dist[e],dist[r],edge[i].v);
if(dist[r]>dist[e]+edge[i].v&&cost[e][r])
{
p[r]=e;
dist[r]=dist[e]+edge[i].v;
//printf("----p[%d]=%d\n",r,e);
if(!visit[r])
{
visit[r]=1;
q.push(r);
// printf("%d\n",r);
}
}
}
//visit[e]=1;
}
if (dist[n+m+1] == INF) return false;
return true;
//if(p[n+m+1]!=-1)return 1;
//return 0;
}
void zeng()
{
// puts("sf");
int minl;
minl=INF;
int i;
for(i=n+m+1;p[i]!=-1;i=p[i])
{
minl=min(minl,cost[p[i]][i]);
//printf("p[%d]=%d\n",i,p[i]);
}
// printf("%d\n",minl);
for(i=n+m+1;p[i]!=-1;i=p[i])
{
int j=p[i];
// printf("cost[%d][%d]=%d\n",j,i,cost[j][i]);
cost[j][i]-=minl;
cost[i][j]+=minl;
// printf("cost[%d][%d]=%d\n",j,i,cost[j][i]);
}
}
int main()
{
int i,j,kk;
while(scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
{
mem(cost,0);
mem(head,-1);
num=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",&give[i][j]);
}
}
for(kk=1;kk<=k;kk++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&fei[kk][i][j]);
// printf("%d %d %d %d\n",kk,i,j,fei[kk][i][j]);
}
}
}
int res=0;
int t;
for(t=1;t<=k;t++)
{
int n1,n2;
n1=n2=0;
for(i=1;i<=m;i++)
{
n1+=give[i][t];
}
for(i=1;i<=n;i++)
{
n2+=need[i][t];
}
if(n2>n1)
{
printf("-1\n");
break;
}
}
if(t!=k+1)continue;
for(t=1;t<=k;t++)
{
mem(cost,0);
mem(head,-1);
num=0;
// printf("*%d_____________________________________*\n",t);
for(i=1;i<=m;i++)
{
add(0,i,0);
add(i,0,0);
cost[0][i]=give[i][t];
cost[i][0]=0;
}
for(i=1;i<=n;i++)
{
add(i+m,n+m+1,0);
add(n+m+1,i+m,0);
cost[i+m][n+m+1]=need[i][t];
cost[n+m+1][i+m]=0;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
add(i,j+m,fei[t][j][i]);
add(j+m,i,-fei[t][j][i]);
cost[i][j+m]=INF;
cost[j+m][i]=0;
// printf("%d %d %d\n",i,j+m,fei[t][j][i]);
}
}
while(spfa())
{
// printf("------\n");
zeng();
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
res+=fei[t][j][i]*(INF-cost[i][j+m]);
}
}
// printf("k=%d,res=%d\n",t,res);
}
printf("%d\n",res);
}
return 0;
}
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define INF 999999
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
int u;
int v;
int next;
bool friend operator < (node a, node b){
return a.u< b.u;
}
}edge[100001];
int head[1000010];
int gcd(int n,int m){if(n<m) swap(n,m);return n%m==0?m:gcd(m,n%m);}
int lcm(int n,int m){if(n<m) swap(n,m);return n/gcd(n,m)*m;}
int n,m,k;
int need[101][101];//第i個店主對物品j的需求；
int give[101][101];//第i個供貨商對物品j的供貨能力；
int fei[101][101][101];//i,j,k;第k個物品，供貨商j對店主i的費用
int cost[501][501];
int p[1001];
int num=0;
void add(int l,int r,int v)
{
edge[num].u=r;
edge[num].v=v;
edge[num].next=head[l];
head[l]=num;
num++;
}
int spfa()
{
int visit[100001];
int i,dist[10001];
memset(visit,0,sizeof(visit));
memset(p,-1,sizeof(p));
queue<int>q;
for(i=0;i<=n+m+1;i++)dist[i]=INF;
dist[0]=0;
q.push(0);
visit[0]=1;
while(!q.empty())
{
int e;
e=q.front();
q.pop();
visit[e]=0;
//printf("tan->%d\n",e);
for(i=head[e];i!=-1;i=edge[i].next)
{
int r=edge[i].u;
// printf("%d %d %d %d %d\n",e,r,dist[e],dist[r],edge[i].v);
if(dist[r]>dist[e]+edge[i].v&&cost[e][r])
{
p[r]=e;
dist[r]=dist[e]+edge[i].v;
//printf("----p[%d]=%d\n",r,e);
if(!visit[r])
{
visit[r]=1;
q.push(r);
// printf("%d\n",r);
}
}
}
//visit[e]=1;
}
if (dist[n+m+1] == INF) return false;
return true;
//if(p[n+m+1]!=-1)return 1;
//return 0;
}
void zeng()
{
// puts("sf");
int minl;
minl=INF;
int i;
for(i=n+m+1;p[i]!=-1;i=p[i])
{
minl=min(minl,cost[p[i]][i]);
//printf("p[%d]=%d\n",i,p[i]);
}
// printf("%d\n",minl);
for(i=n+m+1;p[i]!=-1;i=p[i])
{
int j=p[i];
// printf("cost[%d][%d]=%d\n",j,i,cost[j][i]);
cost[j][i]-=minl;
cost[i][j]+=minl;
// printf("cost[%d][%d]=%d\n",j,i,cost[j][i]);
}
}
int main()
{
int i,j,kk;
while(scanf("%d%d%d",&n,&m,&k)&&(n||m||k))
{
mem(cost,0);
mem(head,-1);
num=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",&give[i][j]);
}
}
for(kk=1;kk<=k;kk++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&fei[kk][i][j]);
// printf("%d %d %d %d\n",kk,i,j,fei[kk][i][j]);
}
}
}
int res=0;
int t;
for(t=1;t<=k;t++)
{
int n1,n2;
n1=n2=0;
for(i=1;i<=m;i++)
{
n1+=give[i][t];
}
for(i=1;i<=n;i++)
{
n2+=need[i][t];
}
if(n2>n1)
{
printf("-1\n");
break;
}
}
if(t!=k+1)continue;
for(t=1;t<=k;t++)
{
mem(cost,0);
mem(head,-1);
num=0;
// printf("*%d_____________________________________*\n",t);
for(i=1;i<=m;i++)
{
add(0,i,0);
add(i,0,0);
cost[0][i]=give[i][t];
cost[i][0]=0;
}
for(i=1;i<=n;i++)
{
add(i+m,n+m+1,0);
add(n+m+1,i+m,0);
cost[i+m][n+m+1]=need[i][t];
cost[n+m+1][i+m]=0;
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
add(i,j+m,fei[t][j][i]);
add(j+m,i,-fei[t][j][i]);
cost[i][j+m]=INF;
cost[j+m][i]=0;
// printf("%d %d %d\n",i,j+m,fei[t][j][i]);
}
}
while(spfa())
{
// printf("------\n");
zeng();
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
res+=fei[t][j][i]*(INF-cost[i][j+m]);
}
}
// printf("k=%d,res=%d\n",t,res);
}
printf("%d\n",res);
}
return 0;
}
