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
#include
#include
#include
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()
{
    queueque;
    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;
}