首页 > 代码库 > 【bzoj4443】[Scoi2015]小凸玩矩阵 二分+二分图匹配
【bzoj4443】[Scoi2015]小凸玩矩阵 二分+二分图匹配
题目描述
小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。
输入
第一行给出三个整数N,M,K
接下来N行，每行M个数字，用来描述这个矩阵
输出
如题
样例输入
3 4 2
1 5 6 6
8 3 4 3
6 8 6 3
样例输出
3
题解
二分+二分图最大匹配
最（第k）大值最小，很容易想到二分答案。
二分一个mid，若满足条件，一定满足：可以选出n-k+1个不在同行同列上的小于mid数。
可以把行看作A集合，把列看作B集合，对于每个小于等于mid的数把它的行列相连。
然后跑匈牙利算法，判断最大匹配是否大于等于n-k+1（即大于n-k)即可。
#include <cstdio>
#include <cstring>
#include <queue>
#define inf 0x7fffffff
using namespace std;
int n , m , k , a[260][260] , head[100000] , to[100000] , next[100000] , cnt , vis[260] , from[260];
void add(int x , int y)
{
to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
}
bool dfs(int x)
{
int i;
for(i = head[x] ; i ; i = next[i])
{
if(!vis[to[i]])
{
vis[to[i]] = 1;
if(!from[to[i]] || dfs(from[to[i]]))
{
from[to[i]] = x;
return 1;
}
}
}
return 0;
}
bool judge(int mid)
{
int i , j , num = 0;
memset(head , 0 , sizeof(head));
cnt = 0;
for(i = 1 ; i <= n ; i ++ )
for(j = 1 ; j <= m ; j ++ )
if(a[i][j] <= mid)
add(i , j);
memset(from , 0 , sizeof(from));
for(i = 1 ; i <= n ; i ++ )
{
memset(vis , 0 , sizeof(vis));
if(dfs(i)) num ++ ;
}
return num > n - k;
}
int main()
{
int i , j , l = inf , r = 0 , mid , ans = 0;
scanf("%d%d%d" , &n , &m , &k);
for(i = 1 ; i <= n ; i ++ )
for(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;
if(judge(mid)) ans = mid , r = mid - 1;
else l = mid + 1;
}
printf("%d\n" , ans);
return 0;
}
【bzoj4443】[Scoi2015]小凸玩矩阵 二分+二分图匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。