【bzoj4443】小凸玩矩阵

  • 本文为博主原创,未经许可不得转载

这是随机程序摇出来的第三道水题

看到题面,很容易想到二分答案,那么怎么实现判定呢?

看到行列限制,我们很容易想到网络流,所以我们把第k大转换成第n-k+1小

如果a[i][j]<=mid,就从i向j连边,跑最大流

如果maxflow>=n-k+1,说明当前mid合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 510
#define INF 1000000000
typedef long long ll;
using namespace std;
struct node{int y,next,v,rel;}e[MAXN*MAXN*2];
int n,m,k,len,S,T,Link[MAXN],level[MAXN],a[255][255];
queue<int> q;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(int x,int y,int v){
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;e[len].rel=len+1;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;e[len].rel=len-1;
}
bool bfs(){
memset(level,-1,sizeof(level));
q.push(S); level[S]=0;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=Link[x];i;i=e[i].next)
if(e[i].v&&level[e[i].y]==-1){
q.push(e[i].y);
level[e[i].y]=level[x]+1;
}
}
return level[T]>=0;
}
int MAXFLOW(int x,int flow){
if(x==T) return flow;
int d=0,maxflow=0;
for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
if(level[e[i].y]==level[x]+1&&e[i].v)
if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow)))
e[i].v-=d,e[e[i].rel].v+=d,maxflow+=d;
if(!maxflow) level[x]=-1;
return maxflow;
}
void pre(){
len=0;
memset(Link,0,sizeof(Link));
}
bool check(int x){
pre(); S=0; T=n+m+1;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
if(a[i][j]<=x) insert(i,j+n,1);
for(int i=1;i<=n;++i) insert(S,i,1);
for(int i=1;i<=m;++i) insert(i+n,T,1);
int d=0,ans=0;
while(bfs()) while(d=MAXFLOW(S,INF)) ans+=d;
return ans>=n-k+1;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
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+1<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
printf("%d\n",check(l)?l:r);
return 0;
}
文章目录
,