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

Description

N个买家，M个卖家，K种货物

接下来N行，每行K个数值，表示每个买家对于K种货物的需求

接下来M行，每行K个数值，表示每个卖家对于K种货物的拥有量

接下来K个矩阵，每个矩阵代表那种货物的有关运输费用

(第k个矩阵第i行第j列的数值,表示第j个卖家运输单位第k种货物到第i个买家的费用)

题目链接：http://poj.org/problem?id=2516 （题目老是AC不了怎么办->去Discuss区看看，我就是不知怎么WA的，去讨论区看，说数组开小了给WA，我开大一些还真AC了，什么鬼……）

Analyze

K种货物分别分析

多源点多汇点->建立超级源点与超级汇点

连接超源到各卖家的路，费用0，容量等于卖家货物量

连接超汇到各买家的路，费用0，容量等于买家需求量

连接卖家与买家间的路，费用对应题目中的费用，容量INF

在可行的前提下，最小费用最大流，原来是最小费用固定流，因为买家到超汇的容量被设为需求量，所以直接求最大流即为该固定流

Code

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 305;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
typedef long long ll;

void Debug(char * s)
{
    cout << "-------------  " << s << "  -------------" << '\n';
}

int A, B, C;
int n, m;

struct edge
{
    int to, w, cap, rev;
};
vector<edge> vec[N];
int h[N], dis[N];
int fro_v[N], fro_e[N];
int t[105][105], s[105][105], cost[55][305][305];
int tt[105], ss[105];

void add(int from, int to, int w, int cap)
{
    int from_sz = vec[from].size(), to_sz = vec[to].size();
    vec[from].push_back( (edge)
    {
        to, w, cap, to_sz
    } );
    vec[to].push_back( (edge)
    {
        from, -w, 0, from_sz
    } );
}

int min_cost_flow(int s, int t)
{
    int flow = 0;
    ll res = 0;
    memset(h, 0, sizeof(h));
    memset(fro_v, 0, sizeof(fro_v));
    memset(fro_e, 0, sizeof(fro_e));
    while(1)
    {
        priority_queue<P, vector<P>, greater<P> > q;
        memset(dis, INF, sizeof(dis));
        dis[s] = 0;
        q.push(P(0, s));
        while(!q.empty())
        {
            P now = q.top();
            q.pop();
            int to = now.second;
            if(dis[to] > now.first)
                continue;
            for(int i = 0; i < vec[to].size(); ++i)
            {
                edge & nxt = vec[to][i];
                if(nxt.cap > 0 && dis[nxt.to] > dis[to] + nxt.w + h[to] - h[nxt.to])
                {
                    dis[nxt.to] = dis[to] + nxt.w + h[to] - h[nxt.to];
                    fro_v[nxt.to] = to;
                    fro_e[nxt.to] = i;
                    q.push(P(dis[nxt.to], nxt.to));
                }
            }
        }
        if(dis[t] == INF)
            return res;
        for(int v = 0; v <= n; ++v)
            h[v] += dis[v];

        int d = INF;
        for(int v = t; v != s; v = fro_v[v])
            d = min(d, vec[fro_v[v] ][ fro_e[v] ].cap);

        flow += d;
        res += d * h[t];
        for(int v = t; v != s; v = fro_v[v])
        {
            edge & nxt = vec[ fro_v[v] ][ fro_e[v] ];
            nxt.cap -= d;
            vec[v][nxt.rev].cap += d;
        }
    }
    return res;
}


int main()
{
    while(~scanf("%d%d%d", &A, &B, &C))
    {
        n = A + B + 1;
        ll ans = 0;
        if(A == 0 && B == 0 && C == 0)
            break;
        memset(tt, 0, sizeof(tt));
        memset(ss, 0, sizeof(ss));
        memset(s, 0, sizeof(s));
        memset(t, 0, sizeof(t));
        memset(cost, 0, sizeof(cost));

        ///循环赋值时,变量出现顺序 必须跟 欲赋值矩阵维度先后对应
        for(int i = 1; i <= A; ++i)
            for(int j = 1; j <= C; ++j)
                scanf("%d", &t[B + i][j]), tt[j] += t[B + i][j];

        for(int i = 1; i <= B; ++i)
            for(int j = 1; j <= C; ++j)
                scanf("%d", &s[i][j]), ss[j] += s[i][j];

        for(int k = 1; k <= C; ++k)
            for(int i = 1; i <= A; ++i)
                for(int j = 1; j <= B; ++j)
                    scanf("%d", &cost[k][B + i][j]);

        bool flag = 1;
        for(int k = 1; k <= C; ++k)
            if(tt[k] > ss[k])
            {
                flag = 0;
                puts("-1");
                break;
            }
        if(!flag)
            continue;

        for(int i = 1; i <= C; ++i)
        {
            for(int j = 0; j < N; ++j)
                vec[j].clear();
            for(int j = 1; j <= B; ++j)
                add(0, j, 0, s[j][i]);
            for(int j = 1; j <= A; ++j)
                add(B + j, B + A + 1, 0, t[B + j][i]);
            for(int j = 1; j <= B; ++j)
                for(int l = 1; l <= A; ++l)
                    add(j, B + l, cost[i][B + l][j], INF);
            int tem =  min_cost_flow(0, B + A + 1);
            ans += tem;
        }
        cout << ans << '\n';
    }
    return 0;
}