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

Posted on Symbols count in article: 716 Reading time ≈ 3 mins.

Problem

【SCOI2015】小凸玩矩阵

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

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

Input

第一行给出三个整数N,M,KN,M,K
接下来NN行，每行MM个数字，用来描述这个矩阵

Output

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

Sample Input

1
2
3
4
3 4 2
1 5 6 6 
8 3 4 3
6 8 6 3

Sample Output

1
3

HINT

1≤K≤N≤M≤250,  1≤矩阵元素≤1091\le K\le N\le M\le250,\;1\le 矩阵元素\le10^9

标签：二分答案 网络流

Solution

套路二分+网络流匹配验证二分+网络流匹配验证。

二分第KK大数的值，将所有A[i][j]≤tansA[i][j]\le tans的位置加入网络流图中 。
建模：给每行每列设一个点，初始S→行i  (i∈[1,n])S\to行_i\;(i\in[1,n])流量11，列j→T  (j∈[1,m])列_j\to T\;(j\in[1,m])流量11。如果A[i][j]≤tansA[i][j]\le tans，则连边行i→列j行_i\to列_j，流量11。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}