[bzoj4443] [loj#2006] [洛谷P4251] [Scoi2015]小凸玩矩阵

Description

小凸和小方是好朋友，小方给小凸一个 \(N \times M\)（ \(N \leq M\) )的矩阵 \(A\) ,要求小秃从其中选出 \(N\) 个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的 \(N\) 个数中第 \(K\) 大的数字的最小值是多少。

Input

第一行给出三个整数 \(N\) , \(M\) , \(K\)

接下来 \(N\) 行，每行 \(M\) 个数字，用来描述这个矩阵

Output

如题

Sample Input

3 4 2

1 5 6 6

8 3 4 3

6 8 6 3

Sample Output

HINT

\(1 \leq K \leq N \leq M \leq 250\) , \(1 \leq 矩阵元素 \leq 10^9\)

想法

题中的“小秃” 怕不是再说我呜呜

看到第 \(k\) 大最小，下意识想到二分。

可二分需要满足有单调性啊？这道题中第 \(k\) 大的数肯定不是越大越满足条件的，满足条件的应是一段区间。

但我们仍可二分这个值的下限 \(x\) ，要满足从 \(\leq x\) 的元素中可选出 \(n-k+1\) 个合法的。

怎么判断能不能选出 \(n-k+1\) 个合法的呢？

我一开始竟一直想怎么数据结构搞…

后来才意识到，“任两个不能在同一行或同一列” 是个挺经典的模型：把行和列当成点，将可选的元素所在的行与列连边，跑二分图匹配就好了。

这样我们得到下限 \(x\) 了，但仍有一个问题，能不能选出 \(k-1\) 个 \(\geq x\) 的元素构成一个合法方案呢？

好巧的是，一定可以。

简略证明如下：

既然 \(x\) 是下限，那么在 \(\leq x-1\) 的元素中一定选不出 \(n-k+1\) 个构成合法方案

那么在当前选了 \(n-k+1\) 个元素后再随便选 \(k-1\) 个元素构成合法方案，这 \(n\) 个元素中 \(\leq x-1\) 的 \(<n-k+1\)

也就是说 \(\geq x\) 的至少有 \(k\) 个。

那么，在我们选出的元素中，二分保证了 \(\leq x\) 的至少有 \(n-k+1\) 个，上面的证明保证 \(\geq x\) 的至少有 \(k\) 个，则第 \(k\) 大的一定是 \(x\)

这个证明太神了……我自己绝对想不到啊 \(qwq\)

要在考场上只能凭感觉猜了 \(qwq\)

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int read(){

	int x=0;

	char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();

	return x;

}

const int N = 255;

int n,m,k;

int a[N][N];

int mp[N][N],vis[N],con[N];

bool find(int u){

	for(int v=1;v<=m;v++){

		if(!mp[u][v] || vis[v]) continue;

		vis[v]=1;

		if(!con[v] || find(con[v])){

			con[v]=u;

			return true;

		}

	}

	return false;

}

bool check(int x){

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			mp[i][j]=(a[i][j]<=x);

	memset(con,0,sizeof(con));

	int f=0;

	for(int i=1;i<=n;i++){

		memset(vis,0,sizeof(vis));

		if(find(i)) f++;

	}

	return f>=n-k+1;

}

int main()

{

	n=read(); m=read(); k=read();

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++) a[i][j]=read();

	int l=1000000009,r=0,mid;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++){

			l=min(l,a[i][j]);

			r=max(r,a[i][j]);

		}

	while(l<r){

		mid=(l+r)>>1;

		if(check(mid)) r=mid;

		else l=mid+1;

	}

	printf("%d\n",l);

	return 0;

}

巴特西