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;
}
