P4251题解

分析：

这道题可以使用二分答案和二分图匹配解决。

由于每行每列只能选一个，可以想到二分图的套路，也就是将行和列连边。

这样来跑二分图匹配，就可以保证一行对应一边。

因为要求出最小的第 $k$ 大值，于是想到二分出一个第 $k$ 大的数，然后小于这个数的就行向列建边，跑出二分图最大匹配。

如果最大匹配大于 $n-k$，就说明这个数字还可以变得再小，缩小二分的边界。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k;
ll mapp[309][309],maxn=-1,head[309],last[90009],to[90009],tot=1,l,r;
ll ans,match[309],vis[309];
void init()
{
	memset(last,0,sizeof(last));
	memset(head,0,sizeof(head));
	memset(to,0,sizeof(to));
}
void add(ll x,ll y)//加边 
{
	tot++;
	to[tot]=y;
	last[tot]=head[x];
	head[x]=tot;
}

bool path(ll u)
{
	for(ll i=head[u];i!=0;i=last[i])//二分图匹配模板 
	{
		ll v=to[i];
		if(vis[v]==1)
			continue;
		vis[v]=1;
		if(match[v]==-1||path(match[v])==true)
		{
			match[v]=u;
			return true; 
		}
	}
	return false;
}
void slove()
{
	ans=0;
	memset(match,-1,sizeof(match));//match数组表示匹配量 
	for(ll i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		if(path(i)==true)
		{
			ans++;
		}
	}
}
int main()                    
{
	cin>>n>>m>>k;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			cin>>mapp[i][j];
			maxn=max(maxn,mapp[i][j]);//maxn表示矩阵最大值 
		}
	}
	l=0,r=maxn;
	while(l<=r)//二分求值 
	{
		init(); //一定要初始化！！！ 
		ll mid=(l+r)/2;
		for(ll i=1;i<=n;i++)
		{
			for(ll j=1;j<=m;j++)
			{
				if(mapp[i][j]<mid)
				{
					add(i,j);//若当前边的权值比二分的数要小，加边 
				}
			}
		 } 
		 slove(); //二分图匹配 
		 if(ans>n-k)//如思路，改变l和r的值 
		 {
		 	r=mid-1;
		 }
		 else
		 {
		 	l=mid+1;
		 }
	}
	cout<<r;//输出 
	return 0;
 }