题目描述
小凸和小方是好朋友，小方给了小凸一个 $n × m$ $(n \leq m)$ 的矩阵 $A$，并且要求小凸从矩阵中选出 $n$ 个数，其中任意两个数都不能在同一行或者同一列。现在小凸想知道，选出的 $n$ 个数中第 $k$ 大的数的最小值是多少。
输入格式
第 $1$ 行读入 $3$ 个整数 $n, m, k$。
接下来 $n$ 行，每一行有 $m$ 个数字，第 $i$ 行第 $j$ 个数字代表矩阵中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$。
输出格式
输出包含一行，为选出的 $n$ 个数中第 $k$ 大数的最小值。
输入样例
2 3 1
1 2 4
2 4 1
输出样例
1
说明
对于 $20\%$ 的数据， $1 \leq n \leq m \leq 9$
对于 $40\%$ 的数据， $1 \leq n \leq m \leq 22, 1 \leq n \leq 12$
对于 $100\%$ 的数据， $1 \leq k \leq n \leq m \leq 250, 1 \leq A_{i,j} \leq 10^9$
Solution
这道题要求求出第k大数的最小值，所以肯定要用二分，又由于选了这个数就不能选其他数，所以我们可以把行和列连边，再用匈牙利进行匹配就可以了。
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000010
namespace STman {
inline char gc(){
#ifdef ONLINE_JUDGE
static char now[1 << 16], *S, *T;
if (T == S) {T = (S = now) + fread(now, 1, 1 << 16, stdin); if (T == S) return EOF;}
return *S++;
#else
return getchar();
#endif
}
template <typename Tp>
inline void read(Tp &x) {
Tp f = 1;x = 0;
char k = gc();
while (k < '0' || k > '9') {if (k == '-') f = -1;k = gc();}
while (k >= '0' && k <= '9') {x = x * 10 + k - '0';k = gc();}
x = x * f;
}
template <typename Tp>
inline void write(Tp x) {
if (x < 0) putchar('-') , x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename Tp>
inline Tp max(Tp a , Tp b) {
if (a > b) return a;
else return b;
}
template <typename Tp>
inline Tp min(Tp a , Tp b) {
if (a < b) return a;
else return b;
}
template <typename Tp>
inline void swap(Tp &a , Tp &b) {
Tp t = a;
a = b;
b = t;
}
template <typename Tp>
inline Tp abs(Tp &a) {
if (a < 0) return -a;
else return a;
}
inline void sp() {
putchar(32);
}
inline void et() {
putchar(10);
}
}
using namespace STman;
struct Edge {
int v, nx, w;
}e[MAXN];
int head[MAXN], mch[MAXN / 100], ecnt, n, m, k, vis[MAXN / 10], l, r, mid, cnt, a, limi = 0;
void add(int f, int t, int w) {
e[++ecnt] = (Edge) {t, head[f], w};
head[f] = ecnt;
}
bool Hungary(int k, int t, int w) {
for (int i = head[k]; i; i = e[i].nx) {
int to = e[i].v;
if (vis[to] != t && e[i].w <= w) {
vis[to] = t;
if (!mch[to] || Hungary(mch[to], t, w)) {
mch[to] = k;
return 1;
}
}
}
return 0;
}
int check(int lim) {
int ans = 0;
memset(vis, 0, sizeof(vis));
memset(mch, 0, sizeof(mch));
for (int i = 1; i <= n; i++) {
if (Hungary(i, i, lim)) ans++;
}
return ans;
}
int main() {
read(n), read(m), read(k);
k = n - k + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
read(a);
add(i, j, a);
limi = max(a, limi);
}
}
l = 1, r = limi;
while (l < r) {
mid = (l + r) >> 1;
if (check(mid) >= k) {
r = mid;
}
else {
l = mid + 1;
}
}
write(l);
return 0;
}
|
