POJ2516 Minimum Cost

这题的大意是有N个店主，有M个供应商，对于N个店主，每个主有一定的需求量（对应着K种商品），M个供应商也对应着一定的供应量。然后相应的供应是有一定的费用。最后问说是否能满足需求，不满足的话输出-1，满足的话输出最小的费用。模型是比较裸，这里对于每个商品，都建个图来费用流，相应的建个超级源点和超级汇点。每次spfa去找，复杂度是O(V*E*E)。

感谢：

http://www.cppblog.com/Icyflame/archive/2009/06/30/88891.html

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 55;
const int INF = INT_MAX;

int N, M, K;
int need[MAX][MAX];
int give[MAX][MAX];
int move[MAX][MAX][MAX];
int SS, TT;
int mm[2 * MAX][2 * MAX];    //flow map
int cc[2 * MAX][2 * MAX];    //cost map
int prev[2 * MAX];
int flow[2 * MAX];
int dis[2 * MAX];
int in[2 * MAX];

void ready()
{
    for(int i = 1; i <= N; i++)  for(int j = 1; j <= K; j++)  scanf("%d", &need[i][j]);
    for(int i = 1; i <= M; i++)  for(int j = 1; j <= K; j++)  scanf("%d", &give[i][j]);
    for(int k = 1; k <= K; k++)  for(int i = 1; i <= N; i++)  for(int j = 1; j <= M; j++)  scanf("%d", &move[k][i][j]);
}

void makeMap(int kind)
{
    SS = 0, TT = N + M + 1;
    //make the flow map
    memset(mm, 0, sizeof(mm));
    for(int i = 1; i <= N; i++)  mm[SS][i] = need[i][kind];
    for(int i = 1; i <= M; i++)  mm[i + N][TT] = give[i][kind];
    for(int i = 1; i <= N; i++)  for(int j = 1; j <= M; j++)  mm[i][j + N] = need[i][kind];
    //make the cost map
    memset(cc, 0, sizeof(cc));
    for(int i = 1; i <= N; i++)  for(int j = 1; j <= M; j++) 
    {
        cc[i][j + N] = move[kind][i][j];
        cc[j + N][i] = -move[kind][i][j];
    }
}

int spfa()
{
    memset(in, 0, sizeof(in));
    memset(dis, -1, sizeof(dis));
    memset(prev, -1, sizeof(prev));    
    memset(flow, 0, sizeof(flow));
    in[SS] = 1, dis[SS] = 0, flow[SS] = INF;
    vector<int> v;
    v.push_back(SS);
    for(int i = 0; i < v.size(); i++)
    {
        int u = v[i];
        in[u] = 0;
        for(int j = SS; j <= TT; j++)
        {
            if(mm[u][j] > 0 && (dis[j] == -1 || dis[u] + cc[u][j] < dis[j]))
            {
                dis[j] = dis[u] + cc[u][j];
                //in[j] = 1;
                prev[j] = u;
                flow[j] = min(flow[u], mm[u][j]);
                if(in[j] == 0)  in[j] = 1, v.push_back(j);
            }
        }
    }
    return flow[TT];
}

int mcmf()
{
    int res = 0;
    while(1)
    {
        int now = spfa();
        if(now == 0)  break;
        int u = TT;
        while(u != SS)
        {
            int v = prev[u];
            mm[v][u] -= now;
            mm[u][v] += now;
            res += now * cc[v][u];
            u = v;
        }
    }
    for(int i = 1; i <= N; i++)
    {
        if(mm[SS][i] > 0)  return -1;
    }
    return res;
}

int main()
{
    while(scanf("%d%d%d", &N, &M, &K), N)
    {
        int res = 0;
        ready();
        for(int k = 1; k <= K; k++)
        {
            makeMap(k);
            int t = mcmf();
            if(t == -1)  
            {
                res = -1;
                break;
            }
            res += t;
        }
        printf("%d\n", res);
    }
}