Libre 6011 「网络流 24 题」运输问题 （网络流，最小费用最大流）
Description
W 公司有m个仓库和n个零售商店。第i个仓库有(a_i)个单位的货物；第j个零售商店需要(b_j)个单位的货物。货物供需平衡。从第i个仓库运送每单位货物到第j个零售商店的费用为(c_{ij})。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。
Input
第1行有2个正整数m和n，分别表示仓库数和零售商店数。接下来的一行中有m个正整数(a_i)，表示第i个仓库(a_i)个单位的货物。再接下来的一行中有n个正整数(b_j)，表示第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
Http
Libre:https://loj.ac/problem/6011
Source
网络流，最小费用最大流
解决思路
这道题的网络流思想还是比较明显的。
对于每一个仓库，从源点连一条容量为该仓库的库存、费用为0的边，对于每一个(c_{ij})，连一条仓库i到商店j的边满足容量为无穷大费用为(c_{ij})。再从每一个商店到汇点连一条容量为商店的需求费用为0的边。
然后分别跑最小费用最大流和最大费用最大流即可。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxN=301;
const int maxM=maxN*maxN*4;
const int inf=2147483647;
class Edge
{
public:
int u,v,cost,flow;
};
int n,m;
int cnt=-1;
int A[maxN];
int B[maxN];
int Map[maxN][maxN];
int Head[maxN];
int Next[maxM];
Edge E[maxM];
int Dist[maxN];
int Flow[maxN];
int Q[maxM];
int Path[maxN];
bool inqueue[maxN];
void Add_Edge(int u,int v,int cost,int flow);
bool spfa1();
bool spfa2();
int main()
{
scanf("%d%d",&m,&n);
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",&Map[i][j]);
//min最小费用
memset(Head,-1,sizeof(Head));
cnt=-1;
for (int i=1;i<=m;i++)
Add_Edge(0,i,0,A[i]);
for (int i=1;i<=n;i++)
Add_Edge(i+m,n+m+1,0,B[i]);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
Add_Edge(i,j+m,Map[i][j],inf);
ll Ans=0;
while (spfa1())
{
int now=n+m+1;
int last=Path[now];
while (now!=0)
{
E[last].flow-=Flow[n+m+1];
E[last^1].flow+=Flow[n+m+1];
now=E[last].u;
last=Path[now];
}
Ans+=Dist[n+m+1]*Flow[n+m+1];
}
cout<<Ans<<endl;
//max最大费用
memset(Head,-1,sizeof(Head));
cnt=-1;
for (int i=1;i<=m;i++)
Add_Edge(0,i,0,A[i]);
for (int i=1;i<=n;i++)
Add_Edge(i+m,n+m+1,0,B[i]);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
Add_Edge(i,j+m,Map[i][j],inf);
Ans=0;
while (spfa2())
{
int now=n+m+1;
int last=Path[now];
while (now!=0)
{
E[last].flow-=Flow[n+m+1];
E[last^1].flow+=Flow[n+m+1];
now=E[last].u;
last=Path[now];
}
Ans+=Dist[n+m+1]*Flow[n+m+1];
}
cout<<Ans<<endl;
return 0;
}
void Add_Edge(int u,int v,int cost,int flow)
{
cnt++;
Next[cnt]=Head[u];
Head[u]=cnt;
E[cnt].u=u;
E[cnt].v=v;
E[cnt].cost=cost;
E[cnt].flow=flow;
cnt++;
Next[cnt]=Head[v];
Head[v]=cnt;
E[cnt].u=v;
E[cnt].v=u;
E[cnt].cost=-cost;
E[cnt].flow=0;
}
bool spfa1()
{
for (int i=0;i<=n+m+1;i++)
Dist[i]=inf;
int h=1,t=0;
Q[1]=0;
inqueue[0]=1;
Flow[0]=inf;
Dist[0]=0;
do
{
t++;
int u=Q[t];
inqueue[u]=0;
for (int i=Head[u];i!=-1;i=Next[i])
{
int v=E[i].v;
if ((E[i].flow>0)&&(Dist[v]>Dist[u]+E[i].cost))
{
Dist[v]=Dist[u]+E[i].cost;
Flow[v]=min(Flow[u],E[i].flow);
Path[v]=i;
if (inqueue[v]==0)
{
h++;
Q[h]=v;
inqueue[v]=1;
}
}
}
}
while (h!=t);
if (Dist[n+m+1]==inf)
return 0;
return 1;
}
bool spfa2()
{
for (int i=0;i<=n+m+1;i++)
Dist[i]=-inf;
int h=1,t=0;
Q[1]=0;
inqueue[0]=1;
Flow[0]=inf;
Dist[0]=0;
do
{
t++;
int u=Q[t];
inqueue[u]=0;
for (int i=Head[u];i!=-1;i=Next[i])
{
int v=E[i].v;
if ((E[i].flow>0)&&(Dist[v]<Dist[u]+E[i].cost))
{
Dist[v]=Dist[u]+E[i].cost;
Flow[v]=min(Flow[u],E[i].flow);
Path[v]=i;
if (inqueue[v]==0)
{
h++;
Q[h]=v;
inqueue[v]=1;
}
}
}
}
while (h!=t);
if (Dist[n+m+1]==-inf)
return 0;
return 1;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
