二分判定,使用网络流
暴力重构图即可
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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | #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)
