先看题目，从数列中选第K小，很容易想到二分或者单调队列，但这里单调队列显得不是那么合适。而任意两个数不在一行一列，这符合二分图的定义，所以思路就很明了了，找出所有的值然后去二分找答案。
#include#include #include #include #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<<1];int next[R<<1];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