传送门 ↬\looparrowright

题目描述

W\text{W} 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 aia_i 个单位的货物；第 jj 个零售商店需要 bjb_j 个单位的货物。
货物供需平衡，即 ∑i=1mai=∑j=1nbj\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j。
从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用为 cijc_{ij} 。
试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

输入格式

第 11 行有 22 个正整数 mm 和 nn，分别表示仓库数和零售商店数。
接下来的一行中有 mm 个正整数 aia_i，表示第 ii 个仓库有 aia_i 个单位的货物。
再接下来的一行中有 nn 个正整数 bjb_j，表示第 jj 个零售商店需要 bjb_j 个单位的货物。
接下来的 mm 行，每行有 nn 个整数，表示从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用 cijc_{ij}。

输出格式

两行分别输出最小运输费用和最大运输费用。

输入输出样例

输入 #1

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

输出 #1

48500
69140

说明/提示

1⩽n,m⩽1001 \leqslant n, m \leqslant 100。

分析

仓库和零售商独立，形成二分图的模型，进而考虑转化为最小费用最大流模型。
设置超级源点 ss 和超级汇点 tt。仓库节点编号为 1∼n1\sim n，零售商节点编号为 n+1∼m+nn+1\sim m+n。从 ss 向各个仓库的节点连边，ss 向节点 ii 的边的容量为 aia_i，费用为 00；从各个零售商的节点向 tt 连边，零售商节点 ii 向 tt 的边的容量为 bi−nb_{i-n}，费用为 00。接着在仓库和零售商之间建边，从仓库向各个零售商节点连边，容量为 +∞+\infty，仓库节点 ii 向零售商节点 jj 的边的边权为 ci,j−nc_{i,j-n}。
根据样例建立的网络如下图，对于最小运输费用，求最小费用最大流即可。若要求最大运输费用，可以将费用取反，求一次最小费用最大流，再将结果取反输出。
洛谷 P4015.png

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P4015
Date: 7/24/2020 
Description: Minimum-cost Flow
*******************************************************************/
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N=204;
const int inf=0x3f3f3f3f;
struct E
{
	int to;
	int cap;
	int cost;
	int Next;
}edge[N*N<<1];
int tot,head[N];
int n,m;//仓库 零售商店数
int s,t;//源点 汇点
int dis[N],incf[N],pre[N];
bool inqueue[N];
int a[N];//仓库货物
int b[N];//商店需要的货物
int c[N][N];//费用
void init();
inline void add_edge(int,int,int,int);
bool SPFA();
int MCMF();
int main()
{
	cin>>n>>m;
	init();
	int i,j;
	for(i=1;i<=n;i++) scanf("%d",a+i);
	for(i=1;i<=m;i++) scanf("%d",b+i);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%d",&c[i][j]);
		}
	}
	for(i=1;i<=n;i++) add_edge(s,i,a[i],0);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			add_edge(i,j+n,inf,c[i][j]);
		}
	}
	for(i=1;i<=m;i++) add_edge(i+n,t,b[i],0);
	cout<<MCMF()<<endl;
	//费用取反 输出最大花费
	init();
	for(i=1;i<=n;i++) add_edge(s,i,a[i],0);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			add_edge(i,j+n,inf,-c[i][j]);
		}
	}
	for(i=1;i<=m;i++) add_edge(i+n,t,b[i],0);
	cout<<-MCMF()<<endl;
	return 0;
}
void init()
{
	memset(head,-1,sizeof(head));
	s=0;
	t=n+m+1;
	tot=1;
}
inline void add_edge(int u,int v,int cap,int cost)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].cost=cost;
	edge[tot].Next=head[u];
	head[u]=tot;
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].cost=-cost;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool SPFA()
{
	queue<int>q;
	memset(dis,inf,sizeof(dis));
	memset(inqueue,0,sizeof(inqueue));
	q.push(s);
	dis[s]=0;
	inqueue[s]=1;
	incf[s]=inf;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inqueue[x]=0;
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			if(!edge[i].cap) continue;//剩余容量为0，不在残量网络中。
			int y=edge[i].to;
		if(dis[y]>dis[x]+edge[i].cost)
			{
				dis[y]=dis[x]+edge[i].cost;//松弛操作
				incf[y]=min(incf[x],edge[i].cap);//最小剩余容量
				pre[y]=i;//记录前驱
				if(!inqueue[y])
				{
					inqueue[y]=1;
					q.push(y);
				}
			}
		}
	}
	if(dis[t]==inf) return 0;//汇点不可达，已经求出最大流
	else return 1;
}
int MCMF()
{
	int maxflow,mincost;
	maxflow=mincost=0;
	while(SPFA())
	{
		int x=t;
		//沿着前驱倒着走增广路
		while(x!=s)
		{
			int y=pre[x];
			edge[y].cap-=incf[t];
			edge[y^1].cap+=incf[t];
			x=edge[y^1].to;
		}
		maxflow+=incf[t];
		mincost+=dis[t]*incf[t];
	}
	return mincost;
}