孙江好

BALENCIAGA  •  3个月前


pragma GCC optimize(2)

include<bits/stdc++.h>

include<ext/rope>

using namespace std; using namespace __gnu_cxx;

define LL long long

define pii pair<int,int>

define mp(a,b) make_pair(a,b)

const int MAXN = 2e5+50; const int MAXM = 2e6+50; const int MOD = 1e9+7; const int INF = 0x3f3f3f3f; int n,m,k,s,t,tot; int head[MAXN],to[MAXM],nxt[MAXM],w[MAXM],h[MAXN]; int a[300][300]; inline void ade(int u,int v,int ww){

to[++tot]=v; w[tot]=ww; nxt[tot]=head[u]; head[u]=tot;

} inline void add(int u,int v,int w){ ade(u,v,w); ade(v,u,0); } inline int bfs(){

queue<int> que; que.push(s); memset(h,0,sizeof(h)); h[s]=1;
while(!que.empty()){
    int u=que.front(); que.pop();
    for(int i=head[u];i;i=nxt[i]){
        if(w[i] && !h[to[i]]){
            h[to[i]]=h[u]+1; que.push(to[i]);
        }
    }
}
return h[t];

} inline int dfs(int x,int f){

if(x==t) return f; int fl=0;
for(int i=head[x];i&&f;i=nxt[i]){
    if(w[i] && h[to[i]]==h[x]+1){
        int mi=dfs(to[i],min(f,w[i]));
        w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
    }
}
if(!fl) h[x]=-1;
return fl;

} inline int dinic(){

int res=0;
while(bfs()) res+=dfs(s,INF);
return res;

} inline bool check(int mid){

memset(head,0,sizeof(head)); s=0; t=n*m+1; tot=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 dinic()>=n-k+1;

} signed main(){

ifndef ONLINE_JUDGE

freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);

endif // ONLINE_JUDGE

scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
int l=1,r=1e9,res=0;
while(l<=r){
    int mid=(l+r)>>1;
    if(check(mid)) r=mid-1,res=mid;
    else l=mid+1;
}
printf("%d\n",res);
return 0;

}


评论:

请先登录,才能进行评论