线性规划与网络流24题の17 运输问题（最小费用最大流、最大费用最大流）

101 阅读 0 评论 67 点赞

我是靠谱客的博主彪壮蓝天，最近开发中收集的这篇文章主要介绍线性规划与网络流24题の17 运输问题（最小费用最大流、最大费用最大流），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

有m个仓库，n个商店，每个仓库有一定的货物ai，每个商店需要供货bi，仓库i到商店j的运输费用是cij。求运输的最小费用和最大费用。

http://wikioi.com/problem/1914/

分别求最小费用最大流和最大费用最大流

//#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double DB;
typedef long long ll;
typedef pair<int, int> PII;
#define pb push_back
#define MP make_pair
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const DB eps = 1e-6;
const int inf = ~0U>>1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int maxn = 1000 + 10;
/*mincost 为最小费用。若要求最大费用，加边时将费用取反，最后-mincost是最大费用*/
///先调用init，然后while(Find());
const int maxv = 1000 + 10;///顶点数
const int maxe = 1000000 + 10;///边数
struct node{
int v, w, cap, next; ///cap = 容量, w = 费用
}edge[maxe];
struct fnode{
int e, cap, w;///上一条边，容量，费用
}fn[maxv];
int head[maxv], cnt, st, ed, maxflow, mincost;
bool vis[maxv];
void addedge(int u, int v, int cap, int w){
edge[cnt].v = v; edge[cnt].w = w; edge[cnt].cap = cap; edge[cnt].next = head[u]; head[u] = cnt++;
edge[cnt].v = u; edge[cnt].w = -w; edge[cnt].cap = 0; edge[cnt].next = head[v]; head[v] = cnt++;
//
printf("u:%d, v:%d, cap:%d, w:%d, cnt:%dn", u, v, cap, w, cnt - 1);
}
bool Find(){///找最短路
memset(vis, false, sizeof(vis));
for(int i=st; i<=ed; i++) fn[i].w = inf;
fn[st].w = 0;
vis[st] = 1; fn[st].cap = inf;
queue<int> Q;
Q.push(st);
while(!Q.empty()){
int now = Q.front(); Q.pop();
vis[now] = 0;
for(int i=head[now]; ~i; i=edge[i].next){
int k = edge[i].v;
if(edge[i].cap && fn[now].w + edge[i].w < fn[k].w){
fn[k].w = fn[now].w + edge[i].w;
fn[k].cap = min(fn[now].cap, edge[i].cap);
fn[k].e = i;
if(!vis[k]){
vis[k] = 1; Q.push(k);
}
}
}
}
if(fn[ed].w == inf) return 0;
mincost += fn[ed].cap * fn[ed].w;
maxflow += fn[ed].cap;
int i = ed;
while(i != st){
edge[fn[i].e].cap -= fn[ed].cap;
edge[fn[i].e ^ 1].cap += fn[ed].cap;
i = edge[fn[i].e ^ 1].v;
}
return 1;
}
void init(int source, int sink){
memset(head, -1, sizeof(head)); cnt = 0;
st = source; ed = sink;///源点和汇点
maxflow = mincost = 0;///最大流和最小费用
}
int n, m, a[maxn], b[maxn], c[maxn][maxn];
int main(){
scanf("%d%d", &m, &n);
init(0, m + n + 1);
for(int i=1; i<=m; i++){
scanf("%d", &a[i]);
addedge(st, i, a[i], 0);
}
for(int i=1; i<=n; i++){
scanf("%d", &b[i]);
addedge(i + m, ed, b[i], 0);
}
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++){
scanf("%d", &c[i][j]);
addedge(i, j + m, inf, c[i][j]);
}
while(Find());
printf("%dn", mincost);
init(0, n + m + 1);
for(int i=1; i<=m; i++)
addedge(st, i, a[i], 0);
for(int j=1; j<=n; j++)
addedge(j + m, ed, b[j], 0);
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
addedge(i, j + m, inf, -c[i][j]);
while(Find());
printf("%dn", -mincost);
return 0;
}