http://poj.org/problem?id=2516
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 110
using namespace std; int need[maxn][maxn];
int sup[maxn][maxn];
int cost[maxn][maxn][maxn];
int cap[maxn][maxn];
int flow[maxn][maxn];
int cost1[maxn][maxn];
int d[maxn];
int p[maxn];
int n,m,k;
const int inf=<<; int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
memset(p,,sizeof(p));
memset(cost1,,sizeof(cost1));
memset(need,,sizeof(need));
if(n==&&m==&&k==) break;
for(int i=; i<=n; i++){
for(int j=; j<=k; j++)
{
scanf("%d",&need[i][j]);
}
}
for(int i=; i<=m; i++)
{
for(int j=; j<=k; j++)
{
scanf("%d",&sup[i][j]);
}
}
for(int c=; c<=k; c++)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
scanf("%d",&cost[c][j][i]);
}
}
}
int s=,t=n+m+;
bool flag=true;
int tt=;
for(int i=; i<=k; i++)
{
memset(cap,,sizeof(cap));
for(int j=; j<=m; j++)
cap[s][j]=sup[j][i];
for(int j=; j<=m; j++)
{
for(int c=; c<=n; c++)
{
cap[j][m+c]=sup[j][i];
}
}
for(int j=; j<=m; j++)
cap[j+m][t]=need[j][i];
memset(flow,,sizeof(flow));
for(int j=; j<=m; j++)
{
for(int c=; c<=n; c++)
{
cost1[j][c+m]=cost[i][j][c];
cost1[c+m][j]=-cost1[j][c+m];
}
}
queue<int>q;
memset(flow,,sizeof(flow));
int mm=;
for(;;)
{
bool inq[maxn];
for(int i=; i<=n+m+; i++) d[i]=(i==s?:inf);
memset(inq,false,sizeof(inq));
q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop();
inq[u]=false;
for(int v=; v<=n+m+; v++) if(cap[u][v]>flow[u][v]&&d[v]>d[u]+cost1[u][v])
{
d[v]=d[u]+cost1[u][v];
p[v]=u;
if(!inq[v])
{
inq[v]=true;
q.push(v);
}
}
}
if(d[t]==inf) break;
int a=inf;
for(int u=t; u!=s; u=p[u])
{
if(cap[p[u]][u]-flow[p[u]][u]<a)
{
a=cap[p[u]][u]-flow[p[u]][u];
}
}
for(int u=t; u!=s; u=p[u])
{
flow[p[u]][u]+=a;
flow[u][p[u]]-=a;
}
mm+=d[t]*a;
}
for(int j=; j<=n; j++)
{
if(flow[j+m][t]!=cap[j+m][t])
{
flag=false;
break;
}
}
if(!flag) break;
if(flag) tt+=mm;
}
if(flag) printf("%d\n",tt);
else printf("-1\n");
}
return ;
}