4443: [Scoi2015]小凸玩矩阵
Time Limit: 10 Sec Memory Limit: 128 MB
Description
小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。
Input
第一行给出三个整数N,M,K
接下来N行，每行M个数字，用来描述这个矩阵
Output
如题
Sample Input
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
Sample Output
3
HINT
1<=K<=N<=M<=250,1<=矩阵元素<=10^9
这题乍一看很有难度，实际上我们冷静分析一下，既然两个数字不能在同一行或同一列，那么如果我们将行和列当做两个集合，这就是让我们求二分图的某一个特殊匹配，使得n" role="presentation" style="position: relative;">nn条匹配边中第k" role="presentation" style="position: relative;">kk大的值最小。既然求最值，那我们不妨二分最值，将该问题转化为判定性问题，判定如果只加值比二分值小的能否使条件成立即可。
代码如下：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,cnt,a[255][255],l=inf,r=0,mid,s=0,t,first[255*255],d[255*255];
struct Node{int v,next,c;}e[255*255*10];
inline void add(int u,int v,int c){
e[++cnt].v=v;
e[cnt].next=first[u];
e[cnt].c=c;
first[u]=cnt;
e[++cnt].v=u;
e[cnt].next=first[v];
e[cnt].c=0;
first[v]=cnt;
}
inline bool bfs(){
queue<int>q;
memset(d,-1,sizeof(d));
d[s]=0;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=first[x];i!=-1;i=e[i].next){
int v=e[i].v;
if(d[v]!=-1||e[i].c<=0)continue;
d[v]=d[x]+1;
if(v==t)return true;
q.push(v);
}
}
return false;
}
inline int dfs(int p,int f){
if(p==t||f==0)return f;
int flow=f;
for(int i=first[p];i!=-1;i=e[i].next){
int v=e[i].v;
if(d[v]==d[p]+1&&e[i].c>0&&flow){
int tmp=dfs(v,min(flow,e[i].c));
if(!tmp)d[v]=-1;
e[i].c-=tmp;
e[i^1].c+=tmp;
flow-=tmp;
}
}
return f-flow;
}
inline bool pd(){
int sum=0;
while(bfs())sum+=dfs(s,inf);
return sum>=n-k+1;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
t=n+m+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]),l=min(l,a[i][j]),r=max(r,a[i][j]);
while(l<r){
mid=(l+r>>1);
memset(e,0,sizeof(e));
memset(first,-1,sizeof(first));
cnt=1;
for(int i=1;i<=n;++i)add(s,i,1);
for(int i=n+1;i<=n+m;++i)add(i,t,1);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(a[i][j]<=mid)add(i,n+j,1);
if(pd())r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}