【线性规划与网络流24题 17】运输问题

72 阅读 0 评论 48 点赞

我是靠谱客的博主结实大炮，最近开发中收集的这篇文章主要介绍【线性规划与网络流24题 17】运输问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

W公司有m个仓库和n 个零售商店。第i 个仓库有a_i个单位的货物;第j个零售商店需要b_j个单位的货物。
货物供需平衡，即sigma(a_i)==sigma(b_j)。
从第i个仓库运送每单位货物到第j个零售商店的费用为C_ij。试设计一个将仓库中所有货物运送到零售商店的运输方案，
使总运输费用最少。

Input

第1行有2 个正整数m和n，分别表示仓库数和零售商店数。
接下来的一行中有m个正整数a_i，1≤i≤m，表示第i个仓库有a_i个单位的货物。
再接下来的一行中有n个正整数b_j，1≤j≤n，表示第j个零售商店需要b_j个单位的货物。
接下来的m行，每行有n个整数，表示从第i个仓库运送每单位货物到第j个零售商店的费用C_ij。

Output

程序运行结束时，将计算出的最少运输费用和最多运输费用输出

Sample Input

2 3
220 280
170 120 210
77 39 105
150 186 122

Sample Output

48500
69140

提交链接：运输问题

这个题看完题意就是个很水的题

因为建立一个源点S，给货物连边（S，Xi，i点的货物总量，INF）

每个货物连到每个商店（Xi，Yj，INF，i->j的单位费用）

建立一个汇点T，从商店连到T（）

然后就是裸的最小费用最大流和最大费用最大流啦！

#include<bits/stdc++.h>
using namespace std;
const int maxm=1050;
const int maxn=1050;
const int INF=0x3f3f3f3f;
int s,t,tot,n,m;
int a[maxm];
int b[maxn];
int mp[maxm][maxn];
struct Edge{
int to,nxt,cap,flow,cost;
}edge[105000];
int Head[maxn],tol;
int pre[maxn],dis[maxn];
bool vis[maxn];
void addedge(int u,int v,int cap,int cost){
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].flow=0;
edge[tol].nxt=Head[u];
Head[u]=tol++;
edge[tol].to=u;
edge[tol].cap=0;
edge[tol].cost=-cost;
edge[tol].flow=0;
edge[tol].nxt=Head[v];
Head[v]=tol++;
}
bool spfa(int s,int t){
queue<int> q;
for(int i=0;i<tot;i++){
dis[i]=INF;vis[i]=false;pre[i]=-1;
}
dis[s]=0;vis[s]=true;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=Head[u];i!=-1;i=edge[i].nxt){
int v=edge[i].to;
if (edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if (!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if (pre[t]==-1) return false;
return true;
}
int minCostMaxflow(int s,int t,int &cost){
int flow=0;
cost=0;
while(spfa(s,t)){
int Min=INF;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
if (Min>edge[i].cap-edge[i].flow)
Min=edge[i].cap-edge[i].flow;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
edge[i].flow+=Min;
edge[i^1].flow-=Min;
cost+=edge[i].cost*Min;
}
flow+=Min;
}
return flow;
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&m,&n)!=EOF){
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&mp[i][j]);
s=0;
t=n+m+1;
tot=t+1;
memset(Head,-1,sizeof(Head));
tol=0;
for(int i=1;i<=m;i++)
addedge(s,i,a[i],0);
for(int i=1;i<=n;i++)
addedge(i+m,t,b[i],0);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
addedge(i,j+m,INF,mp[i][j]);
int cost;
int flow=minCostMaxflow(s,t,cost);
printf("%dn",cost);
memset(Head,-1,sizeof(Head));
tol=0;
for(int i=1;i<=m;i++)
addedge(s,i,a[i],0);
for(int i=1;i<=n;i++)
addedge(i+m,t,b[i],0);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
addedge(i,j+m,INF,-mp[i][j]);
flow=minCostMaxflow(s,t,cost);
printf("%dn",-1*cost);
}
return 0;
}