自动搬运

查看原文

来自洛谷，原作者为

	winxp_qwq 退役菜鸡

搬运于2025-08-24 21:58:11，当前版本为作者最后更新于2018-02-25 22:21:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暂时还没有题解嘛。。。来一篇好了。

首先第k大并不好求，不如二分掉，多用一个log把它变成判定性问题。

那么这样，加上题目中求最小值的要求，我们只需要判断：是否能找出至少n-k+1个数，使得这些数不大于当前值且满足条件。

注意到每行、列最多取一个数，因此取了这个数，就相当于把此行和此列匹配到一起咯。

如此看来，这是一个二分图匹配问题。

由于比较懒，一直没有学二分图匹配的算法，反正dinic也快，这里用dinic解决，把每行和每列看做一个点：

1.从源点向每行连边

2.从每列向汇点连边

3.若矩阵a行b列的数小于等于二分中点，则由a行向b列连边

跑最大流判定即可，最后二分出多少就是多少咯~

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
#define maxn 550
#define inf 1000000007
struct edge{
	int ti;
	int wi;
	int ri;
};
int m,n;
queue <int> q;
vector <edge> ed[maxn];
int dis[maxn]={0}; 
int s=511,t=512;
int xx[maxn][maxn]={{0}};
void addedge(int ss,int tt,int ww){
	edge ee;
	ee.ti=tt;ee.wi=ww;ee.ri=ed[tt].size();
	ed[ss].push_back(ee);
	ee.ri=ed[ss].size()-1;ee.ti=ss;ee.wi=0;
	ed[tt].push_back(ee);
	return;
}
void bfs(){
    int i,j;
    for(i=0;i<maxn;i++)
    dis[i]=inf;
    
    dis[s]=0;
    q.push(s);
    while(1)
    {
        if(q.size()==0) break;
        i=q.front();
        q.pop();
        for(j=0;j<ed[i].size();j++)
        {
            if(ed[i][j].wi>0&&dis[i]+1<dis[ed[i][j].ti])
            {
                dis[ed[i][j].ti]=dis[i]+1;
                q.push(ed[i][j].ti);
            }
        }
    }
}

int find(int x,int low){
    int i,j,k;
    int tt,rr,ww;
    
    if(x==t||low==0) return low;
    
    for(i=0;i<ed[x].size();i++)
    {
        tt=ed[x][i].ti;
        rr=ed[x][i].ri;
        ww=ed[x][i].wi;
        if(ww>0&&dis[tt]==dis[x]+1)
        {
            j=find(tt,min(ww,low));
            if(j>0)
            {
                ed[x][i].wi-=j;
                ed[tt][rr].wi+=j;
                return j;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0,a;
    while(1)
    {
        bfs();
        if(dis[t]==inf) break;
        while(a=find(s,inf))
        ans+=a;
    }
    return ans;
}
int main(){
	int a,b,c,i,j,k;
	scanf("%d%d%d",&n,&m,&k);
	for(a=1;a<=n;a++)
		for(b=1;b<=m;b++)
			scanf("%d",&xx[a][b]);
	int l=1,r=inf,mid;
	while(l<r)
	{
		mid=(l+r)/2;
		for(i=0;i<maxn;i++) ed[i].clear();
		for(a=1;a<=n;a++) addedge(s,a,1);
		for(b=1;b<=m;b++) addedge(b+250,t,1);
		for(a=1;a<=n;a++)
			for(b=1;b<=m;b++)
				if(xx[a][b]<=mid) addedge(a,b+250,1);
		if(dinic()>=n-k+1) r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}