[POJ2516] Minimum Cost

2017年9月28日

有 m 个供应地点,每个供应地点有 k 种货物.有 n 个店主,每个店主需要从供应地点进货,而且对于不同的供应地点,跟不同的供应货物,分别有不同的进货费用.让你求满足所有店主的需求下的最小进货费用.如果不能满足所有店主的需求,输出-1.

把问题简化下,如果只有一种货物,而不是 k 种,那么问题就变成了 n 个店主从 m 个供应地点进一种货的问题,这一种或有数量限制,也有费用限制,显然就是最小费用流的问题,也可以看成二分图的最佳完美匹配,所以这道题除了可以用费用流算法外,还可以用 km 算法来解决.

现在问题是 k 种货物,那么我们可以用 k 次最小费用流算法分别求出 k 种货物的的总费用,期间判断能否满足任意店主的需求,如果不能满足,那也不用后续的费用流算法来计算了.

自己做这道题的时候 T 了好多发啊.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 5000;
int n, m, k;
int path[N];
int nk[55][55], mk[55][55];
int needk[55], hask[55];
int a[N];
int dis[N];
int inq[N];
struct edge {
    int to, flow, cap, cost, next;
} e[N];
int head[N];
int cnt;
void add_edge(int from, int to, int cap, int cost)
{
    e[cnt].to = to, e[cnt].cap = cap, e[cnt].flow = 0, e[cnt].cost = cost, e[cnt].next = head[from], head[from] = cnt++;
    e[cnt].to = from, e[cnt].cap = 0, e[cnt].flow = 0, e[cnt].cost = -cost, e[cnt].next = head[to], head[to] = cnt++;
}
int mcmf(int s, int t, int &cost)
{
    int flow = 0;
    for (;;) {
        memset(a, 0, sizeof(a));
        memset(dis, inf, sizeof(dis));
        memset(inq, 0, sizeof(inq));
        dis[s] = 0;
        a[s] = inf;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            inq[now] = 0;
            for (int u = head[now]; u != -1; u = e[u].next) {
                edge es = e[u];
                if (dis[es.to] > dis[now] + es.cost && es.cap > es.flow) {
                    dis[es.to] = dis[now] + es.cost;
                    path[es.to] = u;
                    a[es.to] = min(a[now], es.cap - es.flow);
                    if (inq[es.to])
                        continue;
                    inq[es.to] = 1;
                    que.push(es.to);
                }
            }
        }
        if (dis[t] == inf)
            break;
        for (int i = t; i != s; i = e[path[i] ^ 1].to) {
            e[path[i]].flow += a[t];
            e[path[i] ^ 1].flow -= a[t];
        }
        cost += a[t] * dis[t];
        flow += a[t];
    }
    return flow;
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
}
int main()
{
    while (~scanf("%d %d %d", &n, &m, &k) && (n + m + k)) {
        int s = 0, t = n + m + 5;
        memset(hask, 0, sizeof(hask));
        memset(needk, 0, sizeof(needk));
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                scanf("%d", &nk[i][j]);
                needk[j] += nk[i][j];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < k; j++) {
                scanf("%d", &mk[i][j]);
                hask[j] += mk[i][j];
            }
        }
        bool ok = 1;
        int ans = 0;
        for (int d = 0; d < k; d++) {
            init();
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    int x;
                    scanf("%d", &x);
                    add_edge(i, n + j, inf, x);
                }
            }
            if (hask[d] < needk[d]) {
                ok = 0;
            }
            if (!ok)
                continue;
            for (int i = 1; i <= n; i++) {
                add_edge(s, i, nk[i][d], 0);
            }
            for (int i = 1; i <= m; i++) {
                add_edge(n + i, t, mk[i][d], 0);
            }
            int cost = 0;
            mcmf(s, t, cost);
            ans += cost;
        }
        printf("%d\n", ok ? ans : -1);
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。