2022牛客多校十 E-Reviewer Assignment（匈牙利算法）

题目链接：登录—专业IT笔试面试备考平台_牛客网

题目：

 样例输入：

5 3
010
010
101
011
100

样例输出：

2 2 1 3 1

题意：给定n个人和m篇文章，然后给出一个n*m的矩阵，a[i][j]=1代表第i个人可以阅读第j篇文章，但是每个人最多只能阅读一篇文章，但是每篇文章可以被多个人阅读，问我们一种方案使得每篇文章被阅读次数不少于一次的文章数尽可能多，在此基础上要求文章被阅读次数不少于两次的 文章数尽可能多，依次类推，但是如果某个人不能阅读任何文章就直接输出-1.

分析：看到这道题目的第一反应就是匈牙利算法，也就是用于求解二分图最大匹配的算法，不知道匈牙利算法的小伙伴可以看下这里：二分图最大匹配（匈牙利算法）_AC__dream的博客-CSDN博客_二分图 最大匹配

如果理解匈牙利算法的思想的话应该就知道匈牙利算法是一个逐步尝试的算法，比如我们要为i进行匹配，但是发现i想匹配的对象已经被其他数匹配，那么我们就让与i想匹配的对象已经匹配的那个人去换一个对象进行匹配，如果能够成功就将其与另一个对象进行匹配，从而让i可以与其想匹配的对象进行匹配，否则不做处理，那么这样的话也就是说一旦某个数有了匹配对象，那么我们只是让其换一个对象进行匹配，并不会使其匹配的数目减少，所以这道题就利用了这一点，我们对文章数进行匹配，每个文章都尽可能地与人进行匹配，如果能匹配成功就直接匹配，否则就进行逐步尝试，我们用一个ans[i]记录阅读第i篇文章的人数，为了使得阅读每篇文章的人数都尽可能多，我们可以一遍一遍地尝试去用文章与人进行匹配，每篇文章最多被阅读的人就是n，这是显然的，所以我们最外层直接跑n次循环就可以了。但是我们需要加一个剪枝，也就是说如果某次循环中m篇文章都没有再次匹配成功直接退出就可以了，表面看起来这样复杂度非常高，但其实真正阅读一篇文章的人数不会特别多，这也就使得复杂度是够用的，需要注意的一点是最后我们要判断一下文章的总阅读次数是不是等于n，也就是判断是不是每个人都阅读了文章。

细节见代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int N=403,M=2e5+10;
int h[N],ne[M],e[M],idx;
int match[N];//match[i]记录与右半部i号节点相匹配的左半部的节点编号 
bool vis[N];//vis[i]标记第i个人有没有阅读文章 
char s[N][N];
int ans[N];
void add(int x,int y)
{
	e[idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
}
bool find(int x)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(vis[j]) continue;
		vis[j]=true;
		if(match[j]==0||find(match[j]))
		{
			match[j]=x;
			return true;
		}
	}
	return false;
}
int main()
{
	int n,m;
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;j++)
			if(s[i][j]=='1') add(j,i);
	}
	int t=0;
	for(int i=1;i<=n;i++)//每篇文章的最多阅读次数
	{
		bool flag=false;
		for(int j=1;j<=m;j++)
		{
			memset(vis,false,sizeof vis);
			if(find(j))
			{
				t++;
				ans[j]++;
				flag=true;
			}
		}
		if(!flag) break;
	}
	if(t==n)
	for(int i=1;i<=n;i++)
		printf("%d ",match[i]);
	else
		printf("-1");
	return 0;
}