【BZOJ4443】[Scoi2015]小凸玩矩阵

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;int n,m,k,cnt;int map[260][260],from[260],head[260],next[260*260],to[260*260],p[260*260],vis[260];int dfs(int x){	for(int i=head[x];i!=-1;i=next[i])	{		if(!vis[to[i]])		{			vis[to[i]]=1;			if(!from[to[i]]||dfs(from[to[i]]))			{				from[to[i]]=x;				return 1;			}		}	}	return 0;}void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}int check(int sta){	int i,j,ans=0;	memset(head,-1,sizeof(head));	cnt=0;	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	if(map[i][j]<=sta)	add(i,j);	memset(from,0,sizeof(from));	for(i=1;i<=n;i++)	{		memset(vis,0,sizeof(vis));		ans+=dfs(i);	}	return ans>=k;}int main(){	scanf("%d%d%d",&n,&m,&k),k=n-k+1;	int i,j;	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	scanf("%d",&map[i][j]),p[++p[0]]=map[i][j];	sort(p+1,p+p[0]+1);	int l=k,r=p[0]+1,mid;	while(l<r)	{		mid=l+r>>1;		if(check(p[mid]))	r=mid;		else	l=mid+1;	}	printf("%d\n",p[r]);	return 0;}