二分判定,使用网络流
暴力重构图即可
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,k,en,h[705],level[705],S,T,cur[705],scr[255][255];
struct Edge{
int b,next,f,back;
}e[1000005];
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
int Bfs(){
queue<int> Q;
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(!e[i].f || level[v])continue;
level[v]=level[u]+1;
Q.push(v);
}
}
return level[T];
}
int Dfs(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
int v=e[i].b,fl;
if(e[i].f && level[v]==level[u]+1 && (fl=Dfs(v,min(f,e[i].f)))){
f-=fl;
e[i].f-=fl;
e[e[i].back].f+=fl;
if(f==0)return flow;
}
}
return flow-f;
}
int Dinic(){
int ans=0;
while(Bfs()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=Dfs(S,2100000000);}
return ans;
}
int Check(int score){
memset(h,0,sizeof(h));
en=0;
for(int i=1;i<=n;i++)AddEdge(S,i,1);
for(int i=1;i<=m;i++)AddEdge(i+n,T,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(scr[i][j]<=score)AddEdge(i,j+n,1);
}
}
return Dinic()>n-k;
}
int main(){
freopen("4443.in","r",stdin);
freopen("4443.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&scr[i][j]);
}
}
S=n+m+1;
T=n+m+2;
int l=1,r=100000000,ans=0;
while(l<=r){
int mid=l+r>>1;
if(Check(mid)){ans=mid;r=mid-1;}
else {l=mid+1;}
}
printf("%d\n",ans);
return 0;
}
评论 (0)
