首页 > 代码库 > LibreOJ #2006. 「SCOI2015」小凸玩矩阵 二分答案+二分匹配
LibreOJ #2006. 「SCOI2015」小凸玩矩阵 二分答案+二分匹配
#2006. 「SCOI2015」小凸玩矩阵
内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： 匿名
提交提交记录统计讨论测试数据
题目描述
小凸和小方是好朋友，小方给小凸一个 N×M N \times MN×M（N≤M N \leq MN≤M）的矩阵 A AA，要求小凸从其中选出 N NN 个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的 N NN 个数中第 K KK 大的数字的最小值是多少。
输入格式
第一行给出三个整数 N NN、M MM、K KK。
接下来 N NN 行，每行 M MM 个数字，用来描述这个矩阵。
输出格式
输出选出来的 N NN 个数中第 K KK 大的数字的最小值。
样例
样例输入
3 4 21 5 6 6 8 3 4 36 8 6 3样例输出
3数据范围与提示
1≤K≤N≤M≤250,1≤Ai,j≤109 1 \leq K \leq N \leq M \leq 250, 1 \leq A_{i, j} \leq 10 ^ 91≤K≤N≤M≤250,1≤A?i,j??≤10?9??
题目链接：https://loj.ac/problem/2006
题意：选出n个行列不相同的数，使得第k大最小。
思路：二分答案+二分匹配。二分答案，然后对行和列进行二分匹配，a[i][j]<=mid的最大匹配与n-k+1进行比较。
代码：
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<set>#include<queue>#include<stack>#include<map>#include<vector>using namespace std;typedef long long ll;typedef pair<int,int> P;const int maxn=300,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7;const ll INF=1e18+7;int n,m,k;ll a[maxn][maxn];vector<int>G[maxn];int match[maxn];int used[maxn];bool dfs(int u,ll mid){ for(int v=1; v<=m; v++) { if(a[u][v]>mid) continue; if(used[v]) continue; used[v]=true; if(match[v]<0||dfs(match[v],mid)) { match[v]=u; return true; } } return false;}bool check(ll mid){ int res=0; memset(match,-1,sizeof(match)); for(int i=1; i<=n; i++) { memset(used,false,sizeof(used)); res+=dfs(i,mid); } //cout<<res<<endl; return res>=n-k+1?1:0;}int main(){ scanf("%d%d%d",&n,&m,&k); ll l=INF,r=0; for(int i=1; i<=n; i++) { ll mmin=INF,mmax=0; for(int j=1; j<=m; j++) { scanf("%d",&a[i][j]); l=min(l,a[i][j]),r=max(r,a[i][j]); } } ll ans=-1; while(l<=r) { ll mid=(l+r)/2; //cout<<l<<" "<<r<<" "<<mid<<endl; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } printf("%lld\n",ans); return 0;}
LibreOJ #2006. 「SCOI2015」小凸玩矩阵 二分答案+二分匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。