【[SCOI2015]小凸玩矩阵】

题目

第\(k\)大显然没有什么办法直接求，于是多一个\(log\)来二分一波

现在的问题变成了判断一个\(mid\)是否能成为第\(k\)大

这还是一个非常经典的棋盘模型，于是经典的做法就是转化成二分图之后行列之间匹配

如果\(a_{i,j}<=mid\)我们就将\(i\)行\(j\)列连边，流量为\(1\)

之后匹配一遍，如果最大流大于等于\(n-k+1\)，说明这个最小值可以是当前的\(mid\)或者还能更小

假设我们需要在匹配完之后继续完成一个完全匹配

由于我们匹配出来的边都是小于等于\(mid\)的，再往那些没有匹配上的行去匹配的时候连得边要么还是小于\(mid\)

那样的话第\(k\)大就能更小

如果需要加的边都是大于\(mid\)的，那么第\(k\)大就是\(mid\)了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define maxn 505

#define re register

#define LL long long

#define inf 999999999

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

struct E{int v,nxt,w,f;}e[maxn*maxn];

inline int read()

{

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int n,m,num,S,T,K,r,l,ans;

int d[maxn],head[maxn],cur[maxn],a[maxn][maxn];

inline void add(int x,int y,int z) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=z;}

inline void C(int x,int y,int z) {add(x,y,z),add(y,x,0);}

inline int BFS()

{

	std::queue<int> q;

	for(re int i=S;i<=T;i++) d[i]=0,cur[i]=head[i];

	d[S]=1,q.push(S);

	while(!q.empty())

	{

		int k=q.front();q.pop();

		for(re int i=head[k];i;i=e[i].nxt)

		if(!d[e[i].v]&&e[i].f<e[i].w) d[e[i].v]=d[k]+1,q.push(e[i].v);

	}

	return d[T];

}

int dfs(int x,int now)

{

	if(x==T||!now) return now;

	int flow=0,ff;

	for(re int& i=cur[x];i;i=e[i].nxt)

	if(d[e[i].v]==d[x]+1)

	{

		ff=dfs(e[i].v,min(e[i].w-e[i].f,now));

		if(ff<=0) continue;

		now-=ff,flow+=ff;

		e[i].f+=ff,e[i^1].f-=ff;

		if(!now) break;

	}

	return flow;

}

inline int check(int mid)

{

	num=1;

	memset(e,0,sizeof(e));

	for(re int i=S;i<=T;i++) head[i]=0;

	for(re int i=1;i<=n;i++) C(S,i,1);

	for(re int i=1;i<=m;i++) C(i+n,T,1);

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

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

			if(a[i][j]<=mid) C(i,j+n,1);

	int tot=0;

	while(BFS()) tot+=dfs(S,inf);

	return tot>=n-K+1;

}

int main()

{

	n=read(),m=read(),K=read();T=n+m+1;

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

		for(re int j=1;j<=m;j++) a[i][j]=read(),r=max(r,a[i][j]);

	l=1,r++;

	while(l<=r)

	{

		int mid=l+r>>1;

		if(check(mid)) r=mid-1,ans=mid;

			else l=mid+1;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

【[SCOI2015]小凸玩矩阵】

最新文章

热门文章