2021牛客暑期多校训练营3 C Minimum grid

2021牛客暑期多校训练营3 C Minimum grid

七月 28, 2021

题目概述

有一个$n \times n$的方阵，其中一些格子可以填数，其他格子均不能填数，且每行有一个最大值要求$b_i$，每列有一个最大值要求$c_i$，即填的数得保证这些最大值要求被满足。现在求最小的填数之和。

数据范围

分析与解

这种看起来具体需要“填一填”弄出具体方案的题目，不妨从必要条件入手去分析。我们猜测，在不填“多余的数”的情况下，这个和至少得是$\sum_{i=1}^n b_i+c_i$​​。很快我们发现这个必要条件可以优化，其实就是如果一个格子对应行列的最大值要求时相等的，那么其实填这个格子就节省了一个最大值。（如果不相等的话是不能实现“1换2”的）

所以我们的目标就是找出所有能够节省最大值的情况——同一行同一列只在上述的一个这种格子上放数，才能实现节省。于是我们用二分图求最大匹配来配置这些格子，即这种格子的行列连边，然后跑二分图匹配。再从答案中减掉匹配成功对应行列的最大值。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MAXN 2010
int n,m,k;
int b[MAXN],c[MAXN];
namespace graph {
	const int N=1e4;
	struct node {
		int v;
		node *nnext;
	} pool[2*N],*h[2*N];
	int cnt=-1;
	void addedge(int u,int v) {
		node *p=&pool[++cnt];
		p->v=v,p->nnext=h[u],h[u]=p;
		node *q=&pool[++cnt];
		q->v=u,q->nnext=h[v],h[v]=q;
	}
	int connect[N];
	bool state[N];
	bool dfs(int u) {
		int v;
		for(node *p=h[u]; p; p=p->nnext) {
			v=p->v;
			if(!state[v]) {
				state[v]=true;
				if(connect[v]==0 || dfs(connect[v])) {
					connect[v]=u;
					return true;
				}
			}
		}
		return false;
	}
	LL hungary() {
		LL ret=0;
		for(int j=1; j<=n; j++) {
			memset(state,0,sizeof(state));
			if(dfs(j))
				ret+=b[j];
		}
		return ret;

	}
}
int main() {
	int u,v;
	LL ans=0;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1; i<=n; i++) {
		scanf("%d",&b[i]);
		ans+=b[i];
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&c[i]);
		ans+=c[i];
	}
	for(int i=1; i<=m; i++) {
		scanf("%d%d",&u,&v);
		if(b[u]==c[v])
			graph::addedge(u,n+v);
	}
	printf("%lld\n",ans - graph::hungary());
	return 0;
}