Description

给定一个 \(n \times m\) 的矩阵，从中选出 \(n\) 个数，使得任意两数不在同一行或同一列。问第 \(k\) 大数字的最小值是多少。

Solution

二分答案，将大于等于 \(mid\) 的数看作 \(1\)，将小于 \(mid\) 的数看作 \(0\)，然后 \(\text{check}\) 一下最大匹配是否超过 \(K\) 即可。

于是满心欢喜地提交，听取 \(WA\) 声一片。你真以为就这么简单？\cy

发现这样求出来的是第 \(K\) 大数字的最大值，因为每次二分需要尽量的减少为 \(1\) 的数，也就是说，我们的答案是尽量地往上“怼”的。

只要将第 \(K\) 大转化为第 \(N - K + 1\) 小即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int _ = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int N, M, K, A[255][255], T[255][255];
int tot, head[_], to[_ << 1], nxt[_ << 1], edge[_ << 1];

void addEdge(int x, int y, int z) {
    to[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
    to[++tot] = x, edge[tot] = 0, nxt[tot] = head[y], head[y] = tot;
}

namespace netFlow {
int S, T, d[_], cur[_];
bool bfs() {
    memset(d, 0, sizeof(d));
    copy(head, head + N + M + 2, cur);
    queue<int> q;
    q.push(S);
    d[S] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = nxt[i])
            if (edge[i] && !d[to[i]]) {
                d[to[i]] = d[x] + 1;
                q.push(to[i]);
                if (to[i] == T) return 1;
            }
    }
    return 0;
}
int dfs(int x, int flow) {
    if (x == T) return flow;
    int rest = flow, k;
    for (int &i = cur[x]; i; i = nxt[i])
        if (edge[i] && d[to[i]] == d[x] + 1) {
            k = dfs(to[i], min(rest, edge[i]));
            if (!k) d[to[i]] = 0;
            edge[i] -= k;
            edge[i ^ 1] += k;
            rest -= k;
        }
    return flow - rest;
}
int dinic(int s, int t) {
    S = s, T = t;
    int flow = 0, maxFlow = 0;
    while (bfs())
        while (flow = dfs(S, INF)) maxFlow += flow;
    return maxFlow;
}
}

bool check(int mid) {
    tot = 1;
    memset(head, 0, sizeof(head));
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            if (A[i][j] <= mid) addEdge(i, j + N, 1);
    for (int i = 1; i <= N; ++i) addEdge(0, i, 1);
    for (int j = 1; j <= M; ++j) addEdge(j + N, N + M + 1, 1);
    return netFlow::dinic(0, N + M + 1) >= K;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
#endif
    int l = 0, r = 0;
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) {
            cin >> A[i][j];
            r = max(r, A[i][j]);
        }
    K = N - K + 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

[SCOI2015]小凸玩矩阵 - 二分 + 二分图最大匹配 + 最大流

原文：https://www.cnblogs.com/newbielyx/p/12210370.html