Minimum Cost 【POJ - 2516】【网络流最小费用最大流】

佚名 5年前 (2019-05-29) 算法 1891人围观抢沙发百度已收录

题意：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

有N个商家它们需要货物源，还有M个货物供应商，N个商家需要K种物品，每种物品都有对应的需求量，M个商家每种物品都是对应的存货，然后再是K个N*M的矩阵表示了K个物品从供货商运送到商家的单位上的价钱，那么就是标准的最大流最小费用了，我们只需要建立这样的边，对于所有的供应商都与源点建立流的大小为拥有的个数的边、与商家建立无穷大的边并且边的代价是单位流的代价，然后再由商家出发到达汇点建立流大小为其需要的边，与汇点和源点建立的边的代价都是0。

思路：

一开始的时候，我计划直接跑一次费用流，但是这样跑了之后，发现了会T，然后考虑到有N个需求商，还有M个提供商，如果想直接一遍跑完的话，点的个数是(N + M + N * K + M * K)这样子点的个数就太多了，但是我们可以换一下，如果分成K次来讨论的话，是不是可以优化下来时间复杂度。

所以，我们分成K次，每次处理对应的货物种类，然后建边分别跑费用流，具体如下。

Minimum Cost 【POJ - 2516】【网络流最小费用最大流】算法第1张

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
const int maxN = 107, S = 0;
int N, M, K, T, need[55], have[55], shop[55][55], good[55][55], r[maxN][maxN], c[maxN][maxN];
int pre[maxN], dist[maxN], Flow[maxN], ans;
queue<int> Q;
bool inque[maxN];
bool spfa()
{
    memset(pre, 0, sizeof(pre)); memset(dist, INF, sizeof(dist)); memset(inque, false, sizeof(inque));
    Q.push(S); inque[S] = true; dist[S] = 0; Flow[S] = INF;
    while(!Q.empty())
    {
        int u = Q.front(); inque[u] = false; Q.pop();
        for(int i=0; i<=T; i++)
        {
            if(r[u][i] && dist[i] > dist[u] + c[u][i])
            {
                dist[i] = dist[u] + c[u][i];
                Flow[i] = min(Flow[u], r[u][i]);
                pre[i] = u;
                if(!inque[i])
                {
                    inque[i] = true;
                    Q.push(i);
                }
            }
        }
    }
    return pre[T];
}
int EK()
{
    int ans = 0;
    while(spfa())
    {
        int now = T, las = pre[now];
        while(now)
        {
            r[las][now] -= Flow[T];
            r[now][las] += Flow[T];
            now = las;
            las = pre[now];
        }
        ans += Flow[T] * dist[T];
    }
    return ans;
}
inline void init()
{
    ans = 0;    T = N + M + 1;
    memset(need, 0, sizeof(need));
    memset(have, 0, sizeof(have));
}
int main()
{
    while(scanf("%d%d%d", &N, &M, &K) && (N || M || K))
    {
        init();
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=K; j++)
            {
                scanf("%d", &shop[i][j]);
                need[j] += shop[i][j];
            }
        }
        for(int i=1; i<=M; i++)
        {
            for(int j=1; j<=K; j++)
            {
                scanf("%d", &good[i][j]);
                have[j] += good[i][j];
            }
        }
        bool flag = true;
        for(int i=1; i<=K; i++)
        {
            if(need[i] > have[i])
            {
                flag = false;
                break;
            }
        }
        for(int i=1; i<=K; i++)
        {
            memset(r, 0, sizeof(r));
            memset(c, 0, sizeof(c));
            for(int j=1; j<=N; j++)
            {
                r[S][j] = shop[j][i];
                for(int kk=1; kk<=M; kk++)
                {
                    scanf("%d", &c[j][N + kk]);
                    c[N + kk][j] = -c[j][N + kk];
                    r[j][N + kk] = INF;
                }
            }
            if(!flag) continue;
            for(int j=1; j<=M; j++) r[N + j][T] = good[j][i];
            ans += EK();
        }
        if(!flag) { printf("-1\n"); continue; }
        printf("%d\n", ans);
    }
    return 0;
}