首页 > 代码库 > [Scoi2015]小凸玩矩阵
[Scoi2015]小凸玩矩阵
bzoj 4443: [Scoi2015]小凸玩矩阵
http://www.lydsy.com/JudgeOnline/problem.php?id=4443
Time Limit: 10 Sec Memory Limit: 128 MBDescription
小凸和小方是好朋友，小方给小凸一个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
二分+最大流
二分一个x，矩阵中的数i若<=x，就从数i的行向列连一条流量为1的边
源点向每一行连一条流量为1的边，列向汇点连一条流量为1的边
最后判断流量是否>=n-k+1，大于return true 否则return false
why?
因为第k大相当于第n-k+1小，我们把所有<=x的边加进去，若最大流>=n-k+1，说明x至少是第n-k+1小，还可能更大
若最大流<n-k+1，说明x不能是第k大，需要找一个更大的
可能会有一个问题：
加边的时候，判断数i<x就加，最后判断流量是否>=n-k 行吗？
不行，因为这里的第k大不是严格意义上的第k大，可能有大小相同的数，去掉=可能少加的不是1条边，是所有与x相等的边
刚开始的时候并不是在行、列之间加边，而是判断完后，把矩阵中的点加进去，在这个点和行、列间各连一条边，TLE
完全没有必要赛这个点进去，因为最后判断的是流量，流量相当于点的个数，至于经过哪个点无所谓，二分总会分到的
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; int n,m,k,src,decc,l,r,tot=1,ans; int a[251][251],b[251000],front[63010],nextt[251000],to[251000],cap[251000],cnt[63010],lev[63010]; queue<int>q; void add(int u,int v,int w) { to[++tot]=v;cap[tot]=w;nextt[tot]=front[u];front[u]=tot; to[++tot]=u;cap[tot]=0;nextt[tot]=front[v];front[v]=tot; } bool bfs() { for(int i=0;i<=n+m+1;i++) {cnt[i]=front[i];lev[i]=-1;} while(!q.empty()) q.pop(); q.push(src);lev[src]=0; while(!q.empty()) { int now=q.front();q.pop(); for(int i=front[now];i!=0;i=nextt[i]) { int t=to[i]; if(cap[i]>0&&lev[t]==-1) { q.push(t); lev[t]=lev[now]+1; if(t==decc) return true; } } } return false; } int dinic(int now,int flow) { if(now==decc) return flow; int delta,rest=0; for(int & i=cnt[now];i!=0;i=nextt[i]) { int t=to[i]; if(lev[t]==lev[now]+1&&cap[i]>0) { delta=dinic(t,min(cap[i],flow-rest)); if(delta) { cap[i]-=delta;cap[i^1]+=delta; rest+=delta;if(rest==flow) break; } } } if(rest!=delta) lev[now]=-1; return rest; } bool check(int u) { int tmp=0;tot=1; memset(front,0,sizeof(front)); for(int i=1;i<=n;i++) { add(src,i,1); for(int j=1;j<=m;j++) { if(a[i][j]>u) continue; add(i,n+j,1); } } for(int i=1;i<=m;i++) add(n+i,decc,1); while(bfs()) tmp+=dinic(src,63000); if(tmp>=n-k+1) return true; return false; } int main() { 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]); b[(i-1)*m+j]=a[i][j]; } decc=n+m+1; sort(b+1,b+n*m+1); l=1,r=n*m; while(l<=r) { int mid=l+r>>1; if(check(b[mid])) { ans=b[mid];r=mid-1;} else l=mid+1; } printf("%d",ans); }
[Scoi2015]小凸玩矩阵
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。