[SCOI2015]小凸玩矩阵

Description:

给你一个n*m的网格,每个格子有一个数字,每行每列只能选一个数字,问所选数字中第k大的数字的最小值是多少

Hint:

\(n \le 250\)

Solution:

显然是二分图模型,但是有附加条件

初看十分不可做,主要原因是这个第k大

我们可以考虑二分一个答案,只对小于这个答案的格子建图

这样就转化成了一个判定性问题,根据每次的最大流与k的大小关系来判断

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const int mxn=1e5+5,inf=1e9;

int n,m,k,cnt;

int S,T,ans,sum,a[555][555],hd[mxn],dep[mxn],cur[mxn];

inline int read() {

	char c=getchar(); int x=0,f=1;

	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}

	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

	return x*f;

}

inline void chkmax(int &x,int y) {if(x<y) x=y;}

inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {

	int to,nxt,w;

}t[mxn<<1];

inline void add(int u,int v,int w) {

	t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;

	t[++cnt]=(ed) {u,hd[v],0}; hd[v]=cnt;

}

int bfs() {

    queue<ll > q; q.push(S);

    memset(dep,0,sizeof(dep)); dep[S]=1;

    for(ll i=S;i<=T;++i) cur[i]=hd[i];

    while(!q.empty()) {

        ll u=q.front(); q.pop();

        for(ll i=hd[u];i!=-1;i=t[i].nxt) {

            ll v=t[i].to;// cout<<t[i].w<<"\n";

            if(!dep[v]&&t[i].w>0)

                dep[v]=dep[u]+1,q.push(v);

        }

    }

    return dep[T];

}

int dfs(ll u,int f) {

    if(u==T) return f;

    for(int &i=cur[u];i!=-1;i=t[i].nxt) {

        ll v=t[i].to;

        if(dep[v]==dep[u]+1&&t[i].w>0) {

            int tp=dfs(v,min(t[i].w,f));

            if(tp>0) {

                t[i].w-=tp;

                t[i^1].w+=tp;

                return tp;

            }

        }

    }

    return 0;

}

void Dinic() {

    while(bfs())

        while(ll tp=dfs(S,inf))

            ans+=tp;

}

int main()

{

	n=read(); m=read(); k=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			a[i][j]=read();

	int l=1,r=inf;

	while(l<r) {

		int mid=(l+r)>>1; T=n+m+1;

		memset(hd,-1,sizeof(hd)); cnt=-1,ans=0;

		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) continue ;

				add(i,j+n,inf);

			}

		Dinic();

		if(ans>=n-k+1) r=mid;

		else l=mid+1;

	}

	printf("%d",r);

    return 0;

}