首页 > 代码库 > POJ 2516 Minimum Cost （最小费用最大流）
POJ 2516 Minimum Cost （最小费用最大流）
POJ 2516 Minimum Cost
链接：http://poj.org/problem?id=2516
题意：有M个仓库，N个商人，K种物品。先输入N，M，K。然后输入N行K个数，每一行代表一个商人要购买的物品，其中K个数分别表示要购买的每件商品数。然后是M行K个数，每行表示仓库里的情况，其中K个数分别每种物品的库存量。接下来是K个矩阵，每个矩阵为N*M，分别表示第K种物品从M个仓库运到第N个商人的花费。问能否合理安排，使得花费最少，如果不行就输出-1。
思路：
一开始的时候，竟然构造了N*K + M*K的点，必然TLE了。
后来发现，其实可以对每一种物品做一次最小费用最大流。然后对每次费用求和即可。
不过一开始要先判断是否能够满足条件。只需要对每一件商品的需求和供应求和，每件商品的供大于等于求便一定能有答案。
代码：
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 5555;
const int maxm = 500000;
struct node {
int v, cap, nxt, cost;
} e[maxm * 2];
int g[maxn], cnt, st, ed, n, m;
int ans, flow;
int N, M, K;
int nk[60][60], mk[60][60];
void add(int u, int v, int cap, int cost) {
e[++cnt].v = v;
e[cnt].cap = cap;
e[cnt].cost = cost;
e[cnt].nxt = g[u];
g[u] = cnt;
e[++cnt].v = u;
e[cnt].cap = 0;
e[cnt].cost = -cost;
e[cnt].nxt = g[v];
g[v] = cnt;
}
void init(int k) {
cnt = 1;
ans = flow = 0;
memset(g, 0, sizeof(int) * (M + N + 10));
// 加边
st = 0, ed = M + N + 1, n = ed;
for (int i = 1; i <= M; i++) add(st, i, mk[i][k], 0);
for (int i = 1; i <= N; i++) add(i + M, ed, nk[i][k], 0);
int c;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
scanf("%d", &c);
add(j, i + M, INF, c);
}
}
}
int dis[maxn], que[maxn], pre[maxn];
bool vis[maxn];
bool spfa() {
int font = 0, rear = 1;
for(int i = 0; i <= n; i ++) {
dis[i] = INF;
vis[i] = false;
}
dis[st] = 0;
que[0] = st;
vis[st] = true;
while(rear != font) {
int u = que[font++];
font %= n;
vis[u] = false;
for(int i = g[u]; i; i = e[i].nxt) {
int v = e[i].v;
if(e[i].cap && dis[v] > dis[u] + e[i].cost) {
dis[v] = dis[u] + e[i].cost;
pre[v] = i;
if(!vis[v]) {
vis[v] = true;
que[rear++] = v;
rear %= n;
}
}
}
}
if(dis[ed] == INF) return false;
return true;
}
void augment() {
int u, p, mi = INF;
for(u = ed; u != st; u = e[p ^ 1].v) {
p = pre[u];
mi = min(mi, e[p].cap);
}
for(u = ed; u != st; u = e[p ^ 1].v) {
p = pre[u];
e[p].cap -= mi;
e[p ^ 1].cap += mi;
ans += mi * e[p].cost; // cost记录的为单位流量费用，必须得乘以流量。
}
flow += mi;
}
int MCMF(int k) {
init(k);
while(spfa()) augment();
return ans;
}
bool get() {
int n_k[110] = {0}, m_k[110] = {0};
int c;
rep(i, 1, N + 1) rep(j, 1, K + 1) {
scanf("%d", &c);
n_k[j] += c;
nk[i][j] = c;
}
rep(i, 1, M + 1) rep(j, 1, K + 1) {
scanf("%d", &c);
m_k[j] += c;
mk[i][j] = c;
}
for (int i = 1; i <= K; i++) if (n_k[i] > m_k[i]) return false;
return true;
}
int main () {
while(~scanf("%d%d%d", &N, &M, &K), N || M || K) {
if (get()) {
int tot = 0;
for (int i = 1; i <= K; i++) {
tot += MCMF(i);
}
printf("%d\n", tot);
} else {
int c;
rep(i, 0, K) rep(j, 0, N) rep(k, 0, M) scanf("%d", &c);
puts("-1");
}
}
return 0;
}
POJ 2516 Minimum Cost （最小费用最大流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。