BZOJ4443【SCOI2015】小凸玩矩阵 <二分+网络流>

Problem

【SCOI2015】小凸玩矩阵

Description

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

Input

第一行给出三个整数
接下来行，每行个数字，用来描述这个矩阵

Output

输出一个整数，表示第大数字的最小值

Sample Input

Sample Output

HINT

标签：二分答案 网络流

Solution

套路。

二分第大数的值，将所有的位置加入网络流图中。
建模：给每行每列设一个点，初始流量，流量。如果，则连边，流量。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
#define MAX_M 100000
#define INF 0x7f7f7f7f
#define mid ((l+r)>>1)
using namespace std;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, k, mx, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];	int mat[255][255];
void init() {cnt = 0, s = 0, t = n+m+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0;	cpy();	while (BFS()) ret += DFS(s, INF), rec();	return ret;}
bool chk(int tans) {
    init();
    for (int i = 1; i <= n; i++) addedge(s, i, 1);
    for (int i = 1; i <= m; i++) addedge(i+n, t, 1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        if (mat[i][j] <= tans) addedge(i, j+n, 1);
    return Dinic() >= n-k+1;
}
int bi_search(int l, int r) {
    int ret = -1;
    while (l <= r)
        if (!chk(mid)) l = mid+1;
        else ret = mid, r = mid-1;
    return ret;
}
int main() {
    read(n), read(m), read(k);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        read(mat[i][j]), mx = max(mat[i][j], mx);
    return printf("%d\n", bi_search(0, mx)), 0;
}