2022牛客多校十 E-Reviewer Assignment（最小费用流）

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

题目：

样例输入： 

3 3
111
110
100

样例输出：

3 2 1

题意：给定n个人和m篇文章，然后给出一个n*m的矩阵，a[i][j]=1代表第i个人可以阅读第j篇文章，但是每个人最多只能阅读一篇文章，但是每篇文章可以被多个人阅读，问我们一种方案使得每篇文章被阅读次数不少于一次的文章数尽可能多，在此基础上要求文章被阅读次数不少于两次的 文章数尽可能多，依次类推，但是如果某个人不能阅读任何文章就直接输出-1.
分析：这道题我在之前利用匈牙利算法分析过，有兴趣的同学可以看这里：2022牛客多校十 E-Reviewer Assignment（匈牙利算法）_AC__dream的博客-CSDN博客

现在我用最小费用流来分析一下这道题目，我们的目的就是使得所有的人尽可能地阅读当前访问次数较低的文章，之前是用匈牙利算法进行一次次迭代求得结果，而像这种对匹配的方案有要求的题目我们可以给其赋予不同的代价，从而使得最小代价就是按照我们的要求匹配得到的，我们可以这样想：每篇文章第一次阅读的代价为1，第二次阅读的代价为2，依次类推，这样我们在选文章阅读的时候肯定尽量选当前能阅读而且阅读代价最小的文章，也就是被阅读次数最小的文章，而又要使得尽可能多的人去阅读文章，这就相当于一个最大流，而我们的要求恰好会使得阅读代价最小，所以我们就可以用网络流来解决这道题目，首先我们建立一个源点，源点向每个审稿人连接容量为1,花费为0的边,每个审稿人向能审的论文连接容量为1,花费为0的边,每篇论文向汇点连接n条容量为1,花费为1,2,...,n的边，其实通过刚才的分析不难得出，花费的选择并不是唯一的，只要是递增的就可以。

剩下的就是一个最小代价模板了。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1403,M=1e6+10;
int h[N],e[M],ne[M],idx; 
long long w[M],c[M],d[N],mf[N];
int pre[N],n,m,s,t,ans[N];
bool vis[N];
char ss[N];
void add(int x,int y,int w1,int w2)
{
	e[idx]=y;
	w[idx]=w1;
	c[idx]=w2;
	ne[idx]=h[x];
	h[x]=idx++;
}
bool spfa()
{
	memset(d,0x3f,sizeof d);
	memset(mf,0,sizeof mf);
	mf[s]=0x3f3f3f3f3f3f3f3f;
	vis[s]=true;d[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=h[x];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(d[j]>d[x]+c[i]&&w[i])
			{
				mf[j]=min(mf[x],w[i]);
				d[j]=d[x]+c[i];
				pre[j]=i;
				if(!vis[j])
				{
					vis[j]=true;
					q.push(j);
				}
			}
		}
	}
	return mf[t]>0;
}
void EK()
{
	while(spfa())
	{
		int x=t;
		while(x!=s)
		{
			int id=pre[x];
			w[id]-=mf[t];
			w[id^1]+=mf[t];
			x=e[id^1];
		}
	}
}
int main()
{
	cin>>n>>m;
	s=n+m+1;
	t=n+m+2;
	for(int i=1;i<=t;i++) h[i]=-1;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ss+1);
		for(int j=1;j<=m;j++)
		if(ss[j]=='1')//建立二分图之间的连边,将右半部的编号1~m映射成n+1~n+m 
		{
			add(i,j+n,1,0);
			add(j+n,i,0,0);
		}
		add(s,i,1,0);//建立源点与二分图左半部的连边 
		add(i,s,0,0); 
	}
	for(int i=1;i<=m;i++)//建立二分图右半部和汇点之间的连边 
	for(int j=1;j<=n;j++)
	{
		add(i+n,t,1,j);
		add(t,i+n,0,-j);
	}
	EK();
	for(int i=1;i<=n;i++)
	{
		for(int j=h[i];j!=-1;j=ne[j])
			if(e[j]!=s&&w[j^1])	ans[i]=e[j]-n;//别忘了再将右半部的点映射回来 
		if(!ans[i])
		{
			puts("-1");
			break;
		}
		if(i==n)
		for(int j=1;j<=n;j++)
			printf("%d ",ans[j]);
	}
	return 0;
}