首页 > 代码库 > 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: 小凸玩矩阵【二分图】