首页 > 代码库 > BZOJ 4443: 小凸玩矩阵【二分图】
BZOJ 4443: 小凸玩矩阵【二分图】
我是传送门
先看题目,从数列中选第K小,很容易想到二分或者单调队列,但这里单调队列显得不是那么合适。而任意两个数不在一行一列,这符合二分图的定义,所以思路就很明了了,找出所有的值然后去二分找答案。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define oo 0x7f7f7f7f#define get(x) scanf( "%d", &x )#define put(x) printf( "%d", x )#define cln(x) memset( x, 0, sizeof(x) )using namespace std;const int R = 255;int f[R];int p[R];int sq[R][R];int head[R];int to[R*R];int next[R*R];int n, m, k, ans, tot;void add( int x, int y ){ tot++; to[tot] = y; next[tot] = head[x]; head[x] = tot;}int DFS( int x, int t ){ for ( int i = head[x]; i != -1; i = next[i] ) { if ( p[to[i]] != t ) { int y = to[i]; p[y] = t; if ( f[y] == 0 || DFS( f[y], t ) ) { f[y] = x; return 1; } } } return 0;}int solve( int l, int r ){ if ( l > r ) return l; int mid = ( l + r ) >> 1; ans = 0; tot = 0; for ( int i = 1; i <= n; i++ ) head[i] = -1; for ( int i = 1; i <= m; i++ ) p[i] = f[i] = 0; for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= m; j++ ) if ( sq[i][j] <= mid ) add( i, j ); for ( int i = 1; i <= n; i++ ) ans += DFS( i, i ); if ( ans >= n - k + 1 ) return solve(l, mid - 1); else return solve( mid + 1, r );}int main(){ get(n), get(m), get(k); for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= m; j++ ) { get(sq[i][j]); ans = max( ans, sq[i][j] ); } put( solve( 1, ans ) ); return 0;}
↑除了MLE所有错误类型都被我弄出来了,真是伤不起Orz
BZOJ 4443: 小凸玩矩阵【二分图】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。