【BZOJ4443】小凸玩矩阵（二分答案，二分图匹配）

题面

BZOJ

Description

小凸和小方是好朋友，小方给小凸一个N*M（N<=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

3

HINT

1<=K<=N<=M<=250,1<=矩阵元素<=10^9

题解

看到这种第\(K\)大都直接二分

二分答案，然后因为行列都只能选一个，很明显的二分图匹配。

拆点之后把权值小于二分值的格子连边，直接二分图匹配就行了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 500

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,m,g[MAX][MAX],K;

struct Line{int v,next;}e[MAX*MAX];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

void Build(int Mid)

{

	memset(h,0,sizeof(h));cnt=1;

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

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

			if(g[i][j]<=Mid)Add(i,j);

}

int match[MAX],vis[MAX],tot;

bool dfs(int u)

{

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(vis[v]==tot)continue;

		vis[v]=tot;

		if(!match[v]||dfs(match[v])){match[v]=u;return true;}

	}

	return false;

}

int check()

{

	memset(match,0,sizeof(match));

	int ret=0;

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

	{

		++tot;

		if(dfs(i))++ret;

	}

	return ret;

}

int main()

{

	n=read();m=read();K=n-read()+1;

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

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

	int l=0,r=1e9,ans=1e9;

	while(l<=r)

	{

		int mid=(l+r)>>1;

		Build(mid);

		if(check()>=K)ans=mid,r=mid-1;

		else l=mid+1;

	}

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

	return 0;

}