题意：有k种物品，m个供应商，n个收购商。每个供应商和收购商都需要一些种类的物品若干。每个供应商与每个收购商之间的对于不同物品的运费是不同的。求满足收购商要求的情况下，最小运费。

分析：最小费用最大流，最大流的前提下求最小费用。这题我们可以把k种物品分开计算，每次对一种物品进行最小费用最大流计算。如果不分开算会超时。对于每种物品，从源到供应商连接，容量为供应商的储存量，费用为0。采购商到汇连边，容量为需求量，费用为0。供应商到采购商连边，容量为无穷，费用为对应的运费。

最小费用最大流的计算流程大致是：每次找到一条最消费的增广路（即以费用为权值的最短路），然后对这条最短路进行增加流量（增加的是流量，不是费用，这里是增广路），直到所有路径流量都不能增加为止。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#include <iomanip>

#define PI acos(-1.0)

#define Max 105

#define inf 1<<28

#define LL(x) (x<<1)

#define RR(x) (x<<1|1)

using namespace std;

int c[Max][Max]; //流量限制

int f[Max][Max];//最大流

int dis[Max];

int w[Max][Max];//费用

bool visit[Max];

int path[Max];

int S,T;

int q[Max*100];

int spfa()//最短路

{

    int i,j;

    for(i=0; i<=T; i++)

        dis[i]=inf,path[i]=-1,visit[i]=0;

    dis[S]=0;

    visit[S]=1;

    int num=0,cnt=0;

    q[num++]=S;

    while(num>cnt)

    {

        int temp=q[cnt++];

        visit[temp]=0;

        for(i=1; i<=T; i++)

            if(c[temp][i]>f[temp][i]&&dis[temp]+w[temp][i]<dis[i])//存在路径与否是看是否有残留量，是否需要松弛则是看花费W

            {

                path[i]=temp;

                dis[i]=dis[temp]+w[temp][i];

                if(!visit[i])

                {

                    visit[i]=1;

                    q[num++]=i;

                }

            }

    }

    if(path[T]==-1)

    return 0;

    return 1;

}

void getMaxflow()//不断找增广路并调整流量

{

    while(spfa())

    {

        int maxFlow=inf;

        int pre=T;

        while(path[pre]!=-1)

        {

            maxFlow=min(maxFlow,c[path[pre]][pre]-f[path[pre]][pre]);

            pre=path[pre];

        }

        pre=T;

        while(path[pre]!=-1)//调整流量，而不是费量

        {

            f[path[pre]][pre]+=maxFlow;

            f[pre][path[pre]]=-f[path[pre]][pre];

            pre=path[pre];

        }

    }

}

int need[Max][Max],have[Max][Max];

int cost[Max][Max][Max];

int main()

{

    int i,j,k,l,n,m,d;

    while(scanf("%d%d%d",&n,&m,&k),(n+m+k))

    {

        for(i=1; i<=n; i++) //客人i

            for(j=1; j<=k; j++) //需要货物j的数量

                scanf("%d",&need[i][j]);

        for(i=1; i<=m; i++) //仓库i

            for(j=1; j<=k; j++) //有货物j的数量

                scanf("%d",&have[i][j]);

        for(i=1; i<=k; i++) //第i个商品

            for(j=1; j<=n; j++) //送到j地点

                for(d=1; d<=m; d++) //从d地点的

                    scanf("%d",&cost[i][d][j]);//的费用

        S=0,T=n+m+1;//超级源点0，超级汇点n+m+1;

        //cout<<1<<endl;

        bool flag=0;

        int ans=0;

        for(i=1; i<=k; i++)

        {

            memset(c,0,sizeof(c));

            memset(f,0,sizeof(f));

            memset(w,0,sizeof(w));

            for(j=1; j<=m; j++)//源点到每个仓库的容量为该仓库这种物品的存量

                c[0][j]=have[j][i];

            for(j=1; j<=n; j++)//每个客人到汇点的容量为该客人对物品的需求量

                c[m+j][T]=need[j][i];

            for(j=1; j<=m; j++)

                for(d=1; d<=n; d++)

                    c[j][d+m]=have[j][i];//每个仓库到每个客人之间的容量为该仓库这种物品的存量，

////每个仓库到每个客人之间的容量为该仓库这种物品的存量，这里不用have[j][i]，直接用99999速度还快点

            for(j=1; j<=m; j++)

                for(d=1; d<=n; d++)

                    w[j][d+m]=cost[i][j][d],w[d+m][j]=-w[j][d+m];//花费，负花费用于回流。

//在一般的最大流中，增广路通过f被反向后，可以回流回去从而更新错误的路线。这里增广路的搜索是按照最短路中的w来确定的，为了能够更新错误的路线，必须对w进行反向操作。从而在if(c[temp][i]>f[temp][i]&&dis[temp]+w[temp][i]<dis[i])

中得以被更正。更正时：temp是客户，i是商家，当负数w[temp][i]足够小，所以dis[temp]+w[temp][i]<dis[i]可以被满足，同时c[temp][i]>f[temp][i]中，c[temp][i]为0，f[temp][i]被反向操作后也可能被满足。

            getMaxflow();

            //算法结束，在最小费用条件，求得的最大流，查看是否存在供货不足的情况

            for(j=1; j<=n; j++)

                if(c[j+m][T]!=f[j+m][T])//如果不能供货，则输出-1

                {

                    flag=1;

                    break;

                }

            if(flag)

                break;

            for(j=1; j<=m; j++)

                for(d=1; d<=n; d++)

                    ans+=f[j][d+m]*w[j][d+m];//总费用

                   // cout<<1<<endl;

        }

        if(flag)

            cout<<"-1"<<endl;

        else

            cout<<ans<<endl;

    }

    return 0;

}

maxflowmincost2516