[SCOI2015]小凸玩矩阵

4443: [Scoi2015]小凸玩矩阵

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1620 Solved: 763
[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

Sample Output

HINT

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

裸的二分 +网络流判定，，但是为什么我一开始又把第K大看成第K小2333

#include<bits/stdc++.h>
#define ll long long
#define maxn 605
#define pb push_back
using namespace std;
const int inf=1<<30;
vector<int> g[maxn];
struct lines{
    int to,flow,cap;
}l[maxn*1000];
int S,T,t=-1,d[maxn],cur[maxn];
bool v[maxn];
   
inline void add(int from,int to,int cap){
    l[++t]=(lines){to,0,cap},g[from].pb(t);
    l[++t]=(lines){from,0,0},g[to].pb(t);
}
   
inline bool BFS(){
    memset(v,0,sizeof(v));
    queue<int> q;
    q.push(S),v[S]=1,d[S]=0;
    int x; lines e;
        
    while(!q.empty()){
        x=q.front(),q.pop();
        for(int i=g[x].size()-1;i>=0;i--){
            e=l[g[x][i]];
            if(e.flow<e.cap&&!v[e.to]){
                v[e.to]=1,d[e.to]=d[x]+1;
                q.push(e.to);
            }
        }
    }
        
    return v[T];
}
    
int dfs(int x,int a){
    if(!a||x==T) return a;
    int flow=0,f,sz=g[x].size();
    for(int &i=cur[x];i<sz;i++){
        lines &e=l[g[x][i]];
        if(d[e.to]==d[x]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))){
            a-=f,flow+=f;
            e.flow+=f,l[g[x][i]^1].flow-=f;
            if(!a) break;
        }
    }
        
    return flow;
}
    
inline int max_flow(){
    int an=0;
    while(BFS()){
        memset(cur,0,sizeof(cur));
        an+=dfs(S,inf);
    }
    return an;
}

int a[maxn][maxn],n,m,k;
int le,ri,mid,an;

inline bool work(){
	for(int i=0;i<=T;i++) g[i].clear();
	t=-1;
	for(int i=1;i<=n;i++) add(S,i,1);
	for(int i=1;i<=m;i++) add(i+n,T,1);
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++) if(a[i][j]<=mid) add(i,j+n,1);
	
	return max_flow()>=n-k+1;
}

int main(){
	scanf("%d%d%d",&n,&m,&k),S=0,T=n+m+1;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	
	le=1,ri=1e9;
	while(le<=ri){
		mid=le+ri>>1;
		if(work()) an=mid,ri=mid-1;
		else le=mid+1;
	}
	
	printf("%d
",an);
	return 0;
}