BZOJ 60 题留念 (۶* ‘ヮ’)۶”

小凸和小方是好朋友，小方给小凸一个 $N \times M (N \leq M)$ 的矩阵 $A$，要求小秃从其中选出 $N$ 个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的 $N$ 个数中第 $K$ 大的数字的最小值是多少。

$1 \leq K \leq N \leq M \leq 250$，$1 \leq A_{i,j} \leq 10^9$

神奇的题解

首先考察如何对于给定的 $bound$ 判断 $bound$ 能否成为第 $K$ 大的数。构建 $N + M$ 个点的二分图，如果 $A_{i,j} \leq bound$ 就从左边第 $i$ 个点向右边第 $j$ 个点连一条边，匹配数 $\geq N - K + 1$ 说明小于等于 $bound$ 的值都可以成为第 $K$ 大的数，即答案不会小于 $bound$。然后就可以愉快地用二分求得答案啦～

（Dinic 大法好）

（`mat` 表示原来的矩阵，`a` 表示建出的二分图）

/**************************************************************
    Problem: 4443
    User: cyand1317
    Language: C
    Result: Accepted
    Time:4008 ms
    Memory:2040 kb
****************************************************************/
 
#include <stdio.h>
#include <string.h>
#define MAXN 512
#define MAXCOL 256
#define INF 0x3fffffff
int min(int a, int b) { return a < b ? a : b; }
 
int n;
int rows, cols, k;
int mat[MAXCOL][MAXCOL];
int a[MAXN][MAXN];
 
int source, sink;
int dist[MAXN];
unsigned char dinic_level()
{
    memset(dist, -1, sizeof dist);
    static int q[MAXN], qhead, qtail;
    qhead = 1, qtail = 0, q[0] = source, dist[source] = 0;
    int i, r;
    while (qhead != qtail) {
        r = q[qtail++];
        for (i = 0; i < n; ++i) if (dist[i] == -1 && a[r][i] > 0) {
            dist[i] = dist[r] + 1;
            q[qhead++] = i;
        }
    }
    return (dist[sink] > 0);
}
int dinic_augment(int u, int cap)
{
    if (u == sink) return cap;
    int i, cur;
    for (i = 0; i < n; ++i)
        if (dist[i] == dist[u] + 1 && a[u][i] > 0
            && (cur = dinic_augment(i, min(cap, a[u][i]))) > 0)
        {
            a[u][i] -= cur;
            a[i][u] += cur;
            return cur;
        }
    return 0;
}
int dinic()
{
    int ans = 0, aug;
    while (dinic_level())
        while ((aug = dinic_augment(source, INF)) > 0) ans += aug;
    return ans;
}
 
unsigned char check_feasibility(int bound)
{
    memset(a, 0, sizeof a);
    n = rows + cols + 2;
    source = n - 2; sink = n - 1;
    int i, j;
    for (i = 0; i < rows; ++i)
        for (j = 0; j < cols; ++j) if (mat[i][j] <= bound) {
            a[i][j + rows] = 1;
        }
    for (i = 0; i < rows; ++i) a[source][i] = 1;
    for (i = 0; i < cols; ++i) a[i + rows][sink] = 1;
    return (dinic() >= rows - k + 1);
}
 
int main()
{
    scanf("%d%d%d", &rows, &cols, &k);
    int i, j;
    for (i = 0; i < rows; ++i)
        for (j = 0; j < cols; ++j) scanf("%d", &mat[i][j]);
 
    int lo = 0, hi = INF, mid;
    while (lo < hi - 1) {
        mid = (lo + hi) >> 1;
        if (check_feasibility(mid)) hi = mid;
        else lo = mid;
    }
    printf("%d\n", lo + 1);
    return 0;
}