[洛谷P4251] 小凸玩矩阵

问题描述

小凸和小方是好朋友，小方给了小凸一个 (n × m (n leq m)) 的矩阵 A，并且要求小凸从矩阵中选出 n 个数，其中任意两个数都不能在同一行或者同一列。现在小凸想知道，选出的 n 个数中第 k 大的数的最小值是多少。

输入格式

第 1 行读入 3 个整数 n, m, k。

接下来 n 行，每一行有 m 个数字，第 i 行第 j 个数字代表矩阵中第 i 行第 j 列的元素 (A_{i,j})。

输出格式

输出包含一行，为选出的 n 个数中第 k 大数的最小值。

数据范围

对于 20% 的数据， (1 leq n leq m leq 9)

对于 40% 的数据， (1 leq n leq m leq 22, 1 leq n leq 12)

对于 100% 的数据， (1 leq k leq n leq m leq 250, 1 leq A_{i,j} leq 10^9)

链接

洛谷

解析

每一行每一列都只能有一个点被选中，这与二分图匹配的限制十分相似。不妨往这一方面去考虑。

首先发现答案是具有单调性的，那么先二分一个mid，把矩阵中大于等于mid的数设为1，小于mid的设为0。然后，可以把新产生的矩阵当做一个邻接矩阵，跑二分图最大匹配。如果匹配数量大于等于(n-mid+1)，说明能找到(n-mid+1)以上个比(mid)大的满足要求的数，即(mid)偏小；反之偏大。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 252
using namespace std;
int n,m,k,i,j,g[N][N],a[N][N],match[N*N];
bool vis[N*N];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
bool dfs(int x)
{
	for(int i=1;i<=m;i++){
		if(g[x][i]&&!vis[n+i]){
			vis[n+i]=1;
			if(!match[n+i]||dfs(match[n+i])){
				match[n+i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int hungary()
{
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!match[i]){
			memset(vis,0,sizeof(vis));
			if(dfs(i)) ans++;
		}
	}
	return ans;
}
bool check(int x)
{
	memset(match,0,sizeof(match));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) g[i][j]=(a[i][j]<=x);
	}
	if(hungary()>=n-k+1) return true;
	return false;
}
int main()
{
	int l=1,r=0,mid,ans;
	n=read();m=read();k=read();
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			a[i][j]=read();
			r=max(r,a[i][j]);
		}
	}
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d
",ans);
	return 0;
}