poj 2516 Minimum Cost(最小用费最大流)

poj 2516 Minimum Cost(最小费用最大流)

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

题意：有n个商店，m个提供商，k种商品
接下来 n*k的矩阵，表示每个商店需要每个商品的数目；
再接下来m*k矩阵，表示每个提供商拥有每个商品的个数。
然后，对于每个物品k，都有n*m的矩阵。
i行j列表示：
从j提供商向i商店运送一个k商品的代价是多少。
判断所有的仓库能否满足所有客户的需求，如果可以，求出最少的运输总费用。

思路：关键是建图，建立一个源点是s = 0 和 汇点 t = n+m+1;
源点到m个供应商，费用为0，容量是这个提供商能够提供这种物品的数量；
每个供应商到每个商店，费用为输入的费用（添加双向边），容量为无穷大；
每个商店到汇点，费用为0，容量为这个商店需要这种商品的数目。
在输入K个矩阵时，一边输入，一边建图对每种商品求最大流。

还要考虑到供不应求的情况，当需求量大于供应量时，不能满足，输出-1.
对于第r种商品，若它的需求量大于最大流量，也不能满足，输出-1；
对每1个商品进行建图寻找增光路，最后累加输出最小费用；

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn = 200;
const int INF = 0x3f3f3f3f;
int n,m,k;
int nn[maxn][maxn],need[maxn];
int hh[maxn][maxn],have[maxn];
int cost[maxn][maxn],res[maxn][maxn];//cost[i][j]表示i到j的费用，res[i][j]表示i到j的当前容量
int s, t;
int mincost,maxflow;
int dis[maxn],pre[maxn];
void build_graph(int x)
{
    memset(res,0,sizeof(res));
    for(int i = 1; i <= m; i++)
        res[s][i+n] = hh[i][x];//源点指向每个供应商，费用为0，容量为该供应商提供的第r种商品
    for(int i = 1; i <= n; i++)
        res[i][t] = nn[i][x];//所有商店指向汇点，费用为0，容量为该供应商需要的第r种商品
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
            res[i+n][j] = INF;//每个供应商指向每个商店，容量为无穷大。
    }
}
void spfa()
{
    queue<int>que;
    while(!que.empty())
        que.pop();
    memset(pre,-1,sizeof(pre));
    int inque[maxn];
    memset(inque,0,sizeof(inque));
    for(int i = s; i <= t; i++)
        dis[i] = INF;
    dis[s] = 0;
    inque[s] = 1;
    que.push(s);

    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        inque[u] = 0;

        for(int i = 0; i <= n+m+1; i++)
        {
            if(res[u][i] && dis[i] > dis[u] + cost[u][i])
            {
                dis[i] = dis[u] + cost[u][i];
                pre[i] = u;
                if(!inque[i])
                {
                    inque[i] = 1;
                    que.push(i);
                }
            }
        }
    }
}

void MCMF()
{
    maxflow = 0;//增光第r种商品的总流量，初始化为0；
    int minflow;//当前增光路上可增加的最小流量；
    while(1)
    {
        spfa();
        if(pre[t] == -1)//找不到增光路，退出
            break;

        minflow = INF;
        for(int u = t; u != s; u = pre[u])
        {
            minflow = min(minflow,res[ pre[u] ][u]);//寻找该增光路上的最小流量
        }
        for(int u = t; u != s; u = pre[u])
        {
            res[ pre[u] ][u] -= minflow;
            res[u][ pre[u] ] += minflow;
        }
        maxflow += minflow;
        mincost += minflow*dis[t];
    }
}

int main()
{
    while(~scanf("%d %d %d",&n,&m,&k))
    {
        if(n == 0 && m == 0 && k == 0)
            break;
        bool flag = 0;
        s = 0;//源点
        t = n+m+1;//汇点
        mincost = 0;//最小费用初始化；
        memset(need,0,sizeof(need));
        memset(have,0,sizeof(have));
        //nn[i][j]表示第i个商店需求nn[i][j]个第j种商品；
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= k; j++)
            {
                scanf("%d",&nn[i][j]);
                need[j] += nn[i][j];
            }
        }
        //hh[i][j]表示第i个供应商拥有hh[i][j]个第j中商品；
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= k; j++)
            {
                scanf("%d",&hh[i][j]);
                have[j] += hh[i][j];
            }
        }
        //如果第i种商品的需求量大于供应量，标记为1，但后面的仍然要继续输入
        for(int i = 1; i <= k; i++)
        {
            if(need[i] > have[i])
            {
                flag = 1;
                break;
            }
        }
        //下面输入k个n*m的矩阵，其第i行第j列表示第j个供应商向第i个商店运送第k个商品的单位费用；
        for(int r = 1; r <= k; r++)
        {
            memset(cost,0,sizeof(cost));
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= m; j++)
                {
                    scanf("%d",&cost[j+n][i]);
                    cost[i][j+n] = -cost[j+n][i];//注意添加双向边
                }
            }
            if(flag) continue;//如果已经不合法，就不用建图，但数据要继续输入

            build_graph(r);
            MCMF();
            if(need[r] > maxflow) flag = 1;//如果第r种商品的需求量大于最大流量，也不合法。
        }
        if(flag) printf("-1\n");
        else printf("%d\n",mincost);
    }
    return 0;
}