牛客多校10 - Reviewer Assignment（最大匹配）

https://ac.nowcoder.com/acm/contest/33195/E

题意
一共 n 个评委，m 篇文章。
每篇文章可以由若干位（可能为0）评委审核，但是每位评委只能审核一篇文章。

问，如何匹配能够使得：

• 被大于等于 1 位评委审核的文章尽量多；
• 在上述前提下，被大于等于 2 位评委审核的文章尽量多；
• 在上述前提下，被大于等于 3 位评委审核的文章尽可能多；
• …

输出每位评委审核的文章编号。如果存在某位评委没有审核，输出-1。

$1\le n,m\le 400$

思路
如果说，每篇文章只能由一位评委审核，而每位评委只能审核一篇文章，那就是最大匹配的板子了，但这题，每篇文章可以匹配若干个评委，还要满足让尽量多的文章被匹配，然后每篇文章匹配尽可能多的评委。

如果先跑一遍最大匹配，那么尽可能多的文章都可以被匹配，满足被大于等于 1 位评委审核的文章尽量多了。

而如果在第一遍匹配的基础上再跑一遍，那么原来每篇文章的匹配数是不变的，然后有些文章发现又可以和其他评委匹配，那么这些文章的匹配数就增加 1，就满足大于等于 2 位评委审核的文章尽可能多。

然后再跑一遍最大匹配，就满足大于等于 3 位评委审核的文章尽可能多；
…

直到，跑一遍最大匹配发现没有文章的匹配数增加，就停止。

时间复杂度很迷，n 和 m 是 400，一次最大匹配时间复杂度为(VE)，点数*边数，那么最坏情况下就是 $(n^{2}m)$ 6e7，但是我试了下跑 500 次最大匹配都跑出答案，3e10？
应该是后面跑最大匹配的时候，前面的 match 标记减少了复杂度，或者是数据水了。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
vector<int> e[N];
int f[N], match[N];
int ans[N];

bool find(int x)
{
	for(int tx : e[x])
	{
		if(f[tx]) continue;
		
		f[tx] = 1;
		if(!match[tx] || find(match[tx])){
			match[tx] = x;
			return 1;
		}
	}
	return 0;
}

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;cin >> c;
			if(c == '1') e[j].push_back(i);
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		int flag = 0;
		for(int j=1;j<=m;j++)
		{
			for(int k=1;k<=n;k++) f[k] = 0;
			if(find(j)) flag = 1;
		}
		if(!flag) break;
	}
	
	int flag = 0;
	for(int i=1;i<=n;i++) if(!match[i]) flag = 1;
	
	if(flag) cout << -1;
	else for(int i=1;i<=n;i++) cout << match[i] << ' ';
	
	return 0;
}
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