题目链接

题目大意

WW 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 aia_i​ 个单位的货物；第 jj 个零售商店需要 bjb_j 个单位的货物。

货物供需平衡.

从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用为 cijc_{ij}​​ 。

试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

题解

费用流模板题。

建源点和汇点连边。

源点向每个仓库ii连边，流量为仓库ii的货物数量，费用为00.
每个商店jj向汇点连边，流量为商店jj的需求量，费用为00.

以上两种边的目的都是限制流量，同时因为货物供需平衡，最后一定能全部满足。

最后每个仓库ii向商店jj连边，流量为infinf，费用为cijc_{ij}. 如果这种边通过流量，那么就说明仓库ii运送了货物到商店jj.

最后跑费用流就好了。

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn=105;
const int maxm=1000005;
const int inf=0x7f7f7f7f;
const long long linf=1e18;

struct node
{
	int to,next,flow;
	long long cost;
} edge[maxm<<1];

bool vis[maxn<<2];
int head[maxn<<2],k,s,t;
long long dist[maxn<<2],tot_cost;

void add(int u,int v,int w,long long c)
{
	edge[++k].to=v;
	edge[k].next=head[u];
	head[u]=k;
	edge[k].flow=w;
	edge[k].cost=c;
	swap(u,v);
	edge[++k].to=v;
	edge[k].next=head[u];
	head[u]=k;
	edge[k].flow=0;
	edge[k].cost=-c;
}
bool spfa()
{
	for(int i=0;i<=t;i++) dist[i]=linf;
	memset(vis,false,sizeof(vis));
	queue<int> q;dist[t]=0;q.push(t);
	while(!q.empty())
	{
		int x=q.front();q.pop();vis[x]=false;
		for(int i=head[x];i;i=edge[i].next)
		{
			if(dist[edge[i].to]>dist[x]-edge[i].cost&&edge[i^1].flow)
			{
				dist[edge[i].to]=dist[x]-edge[i].cost;
				if(!vis[edge[i].to])
				{
					vis[edge[i].to]=true;
					q.push(edge[i].to);
				}
			}
		}
	}
	return dist[s]!=linf;
}
int dfs(int x,int f)
{
	vis[x]=true;
	if(x==t||!f) return f;
	int flow=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		if(vis[edge[i].to]) continue;
		if(dist[edge[i].to]==dist[x]-edge[i].cost&&edge[i].flow)
		{
			int temp=dfs(edge[i].to,min(f-flow,edge[i].flow));
			edge[i].flow-=temp;
			edge[i^1].flow+=temp;
			flow+=temp;
			tot_cost+=(long long)temp*edge[i].cost;
			if(f==flow) break;
		}
	}
	return flow;
}
void zkw()
{
	tot_cost=0;
	while(spfa())
	{
		vis[t]=true;
		while(vis[t])
		{
			memset(vis,false,sizeof(vis));
			dfs(s,inf);
		}
	}
	if(tot_cost>=0) printf("%lld\n",tot_cost);
	else printf("%lld\n",-tot_cost);
}
int n,m,a[maxn],b[maxn],cost[maxn][maxn];

int main()
{
	#ifdef lemon
	freopen("4015.txt","r",stdin);
	#endif
	scanf("%d%d",&m,&n);s=0;t=m+n+1;k=1;
	for(int i=1;i<=m;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	//1-n store
	//n+1-m repo
	//0 source
	//n+m+1
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&cost[i][j]);
	for(int i=1;i<=n;i++) add(i,t,b[i],0);
	for(int i=1;i<=m;i++) add(s,i+n,a[i],0);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			add(i+n,j,inf,cost[i][j]);
	zkw();
	memset(head,0,sizeof(head));k=1;
	for(int i=1;i<=n;i++) add(i,t,b[i],0);
	for(int i=1;i<=m;i++) add(s,i+n,a[i],0);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			add(i+n,j,inf,-cost[i][j]);
	zkw();
	return 0;
}