Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 149 Solved: 81
[Submit][Status][Discuss]
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
1 5 6 6
8 3 4 3
6 8 6 3
Sample Output
3
HINT
1<=K<=N<=M<=250,1<=矩阵元素<=10^9
题解：
N个数中的第K大，就是第N-K+1小，这点要是没看见就毁了。设这个数为x，二分这个数，判断是否合法。
判断合法的方法，N^2枚举矩阵中的每个数，如果这个a[i][j]数小于等于x，让i连一条到j，容量为1的边。因为要保证N个数的i，j各不相同，所以设行i为x集，列j为y集，所有边权均为1，做最大流，也就是二分图的最大匹配。如果跑出来的maxflow大于等于N-K+1,说明x满足条件。注意以上两个不等关系都是大于等于，因为要考虑这样一种情况，整个矩阵的数字都是1，第1小是1，第N小还是1。我被这个坑了好久。。。
/**************************************************************
Problem: 4443
User: __abcdef__
Language: C++
Result: Accepted
Time:216 ms
Memory:14640 kb
****************************************************************/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
const int inf=1e9,maxn=;
int N,M,K,S,T,tot,MIN=inf,MAX;
int a[maxn][maxn],tmp[maxn][maxn];
struct MAT{
int x,y,v,f;
}mat[maxn*maxn];
inline int cmp(const MAT & e,const MAT & w){
return e.v<w.v;
} struct Edge{
int to,rest,next;
}e[maxn*maxn*];
int head[maxn*maxn],cnt=;
inline void Addedge(int x,int y,int r){
e[++cnt].to=y; e[cnt].rest=r; e[cnt].next=head[x]; head[x]=cnt;
e[++cnt].to=x; e[cnt].rest=; e[cnt].next=head[y]; head[y]=cnt;
} int dis[maxn*maxn];
inline bool BFS(){
memset(dis,,sizeof(dis));
static queue<int> Q;
while(!Q.empty()) Q.pop();
Q.push(S); dis[S]=;
while(!Q.empty()){
int x=Q.front(); Q.pop();
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]==&&e[i].rest){
dis[y]=dis[x]+;
Q.push(y);
}
}
}
if(dis[T]!=) return true;
return false;
}
inline int DFS(int x,int flow){
if(x==T) return flow;
int now=,temp;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]==dis[x]+&&e[i].rest){
temp=DFS(y,min(flow-now,e[i].rest));
e[i].rest-=temp;
e[i^].rest+=temp;
now+=temp;
if(now==flow) return flow;
}
}
if(!now) dis[x]=;
return now;
} inline int dinic(){
int ans=;
while(BFS()==true) ans+=DFS(S,inf);
return ans;
} inline bool jud(int x){ for(int i=;i<=cnt+;i++) e[i].to=e[i].rest=e[i].next=;
memset(head,,sizeof(head)); cnt=;
S=; T=N+M+;
for(int i=;i<=N;i++) Addedge(S,i,);// S 连向 x集 权值为 1
for(int i=;i<=M;i++) Addedge(N+i,T,);//y集 连向 T 权值为 1
for(int i=;i<=N;i++){// x集 连向 y集
for(int j=;j<=M;j++){
if(tmp[i][j]<=x){
Addedge(i,N+j,);
}
}
}
int maxflow=dinic();
if(maxflow>=N-K+) return true;
else return false;
}
inline int find(int l,int r){
if(l+>=r){
if(jud(l)==true) return l;
else return r;
}
int mid=(l+r)>>;
if(jud(mid)==true) return find(l,mid);
else return find(mid+,r);
}
int main(){
scanf("%d%d%d",&N,&M,&K);
for(int i=;i<=N;i++){
for(int j=;j<=M;j++){
scanf("%d",&a[i][j]);
mat[++tot].x=i; mat[tot].y=j; mat[tot].v=a[i][j];
}
}
tot=;
sort(mat+,mat+N*M+,cmp);
for(int i=;i<=N*M;i++){
if(mat[i].v!=mat[i-].v) mat[i].f=++tot;
else mat[i].f=tot;
}
for(int i=;i<=N*M;i++){
tmp[mat[i].x][mat[i].y]=mat[i].f;
MIN=min(MIN,mat[i].f); MAX=max(MAX,mat[i].f);
}
int ggg=find(MIN,MAX);
for(int i=;i<=N;i++){
for(int j=;j<=M;j++){
if(tmp[i][j]==ggg){
printf("%d\n",a[i][j]);
return ;
}
}
}
return ;
}