首页 > 代码库 > BZOJ 4443 [Scoi2015]小凸玩矩阵（二分答案+二分图匹配）
BZOJ 4443 [Scoi2015]小凸玩矩阵（二分答案+二分图匹配）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4443
【题目大意】
从矩阵中选出N个数，其中任意两个数字不能在同一行或同一列
求选出来的N个数中第K大的数字的最小值是多少。
【题解】
我们二分这个第k大数字的大小，将其以上的数字全部删除，
在剩余的部分按行列连边，如果二分图匹配的数量大于n-k那么说明该答案可行。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>#include <vector> using namespace std;const int MAX_V=1000;const int INF=0x3f3f3f3f;int V,match[MAX_V];vector<int> G[MAX_V];bool used[MAX_V];void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u);}bool dfs(int v){ used[v]=1; for(int i=0;i<G[v].size();i++){ int u=G[v][i],w=match[u]; if(w<0||!used[w]&&dfs(w)){ match[v]=u; match[u]=v; return 1; } }return 0;}int bipartite_matching(){ int res=0; memset(match,-1,sizeof(match)); for(int v=0;v<V;v++){ if(match[v]<0){ memset(used,0,sizeof(used)); if(dfs(v))res++; } }return res;}const int N=300;int n,m,k,a[N][N];bool check(int x){ V=n+m+1; for(int i=0;i<V;i++)G[i].clear(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)if(a[i][j]<=x){ add_edge(i,n+j); } }return bipartite_matching()>=n-k+1;}int main(){ while(~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]); } int l=1,r=1000000000,ans=r; while(l<=r){ int mid=(l+r)>>1; if(check(mid))r=mid-1,ans=mid; else l=mid+1; }printf("%d\n",ans); }return 0;}BZOJ 4443 [Scoi2015]小凸玩矩阵（二分答案+二分图匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。