[BZOJ4443] [Scoi2015]小凸玩矩阵

题目描述

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大 很显然用二分来求 第k大=第n-k+1小
所以我们二分出第k大的值mid后,只需要满足有n-k+1个符合条件的数字≤mid就行了
这个用二分图最大匹配 如果有map[i][j]<=mid  那么i->j连一条有向边
最后对行数跑匈牙利算法求出总数 与n-k+1比较就好了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int c[500][500];
int n,m,k;
struct your
{
	int net,to;
}a[260*260];
int tot;
int head[260],que[260*260];
void add(int x,int y)
{
	a[++tot].net=head[x];
	a[tot].to=y;
	head[x]=tot;
}
bool vis[260];
int line[260];
int dfs(int x)
{
	for(int i=head[x];i;i=a[i].net)
		if(!vis[a[i].to])
		{
			vis[a[i].to]=1;
			if(line[a[i].to]==0||dfs(line[a[i].to]))
			{
				line[a[i].to]=x;
				return 1;
			}
		}
	return 0;
}
int check(int mid)
{
	memset(head,0,sizeof head);
	memset(a,0,sizeof a);
	tot=0;
	int tmp=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(c[i][j]<=mid) add(i,j);
	memset(line,0,sizeof line);
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof vis);
		if(dfs(i)) tmp++;
	}
	return tmp>n-k;
}
int find()
{
	int l=1,r=que[0];
	int mid=(l+r)>>1;
	int ans;
	while(l<r)
	{
		if(check(que[mid])) r=mid,ans=que[mid];
		else l=mid+1;
		mid=(l+r)>>1;
	}
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
 for(int i=1;i<=n;i++)
 	for(int j=1;j<=m;j++)
 		scanf("%d",&c[i][j]),que[++que[0]]=c[i][j];
 sort(que+1,que+que[0]+1);
 printf("%d",find());
 return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注