本题解法显然是二分 + 二分图匹配，但是目前出现了两种写法。

第一种写法（应该是正确的写法）：

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

inline int get() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

const int N = 255, N1 = N * N * 10;
int n, m, k, l = 1e9, r;
int mat[N][N], ans;
bool vis[N], b[N][N];
int bin[N1], top;

struct Edge {
	int v, nxt;
} edge[N1];
int head[N * 2], f[N * 2], tot;

inline void addedge(int u, int v) {
	edge[++tot].v = v;
	edge[tot].nxt = head[u];
	head[u] = tot;
}

inline void insedge(int u, int v) {
	addedge(u, v);
	addedge(v, u);
}

inline bool dfs(int u) {
	if(vis[u]) return 0;
	vis[u] = 1;
	for(register int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].v;
		if(!f[v] || dfs(f[v])) {
			f[v] = u;
			return 1;
		}
	}
	return 0;
}

inline bool chk(int x) {
	memset(head, 0, sizeof(head));
	memset(edge, 0, sizeof(edge));
	memset(f, 0, sizeof(f));
	memset(vis, 0, sizeof(vis));
	tot = 0;
	for(register int i = 1; i <= n; i++) 
		for(register int j = 1; j <= m; j++)
			if(mat[i][j] <= x) insedge(i, j + n);
	int cnt = 0;
	for(register int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		cnt += dfs(i);
	}
	if(cnt > n - k) return 1;
	return 0;
}

int main() {
	n = get(), m = get(), k = get();
	for(register int i = 1; i <= n; i++) 
		for(register int j = 1; j <= m; j++) 
			mat[i][j] = get(), bin[++top] = mat[i][j];
	sort(bin + 1, bin + 1 + top);
	l = 1, r = top;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(chk(bin[mid])) ans = bin[mid], r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << endl; 
	return 0;
}

然而在我校 OJ 上有另外一种写法：

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

inline int get() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

const int N = 255, N1 = N * N * 10;
int n, m, k, l = 1e9, r;
int mat[N][N], ans;
bool vis[N], b[N][N];
int bin[N1], top;

struct Edge {
	int v, nxt;
} edge[N1];
int head[N * 2], f[N * 2], tot;

inline void addedge(int u, int v) {
	edge[++tot].v = v;
	edge[tot].nxt = head[u];
	head[u] = tot;
}

inline void insedge(int u, int v) {
	addedge(u, v);
	addedge(v, u);
}

inline bool dfs(int u) {
	if(vis[u]) return 0;
	vis[u] = 1;
	for(register int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].v;
		if(!f[v] || dfs(f[v])) {
			f[v] = u;
			return 1;
		}
	}
	return 0;
}

inline bool chk(int x) {
	memset(head, 0, sizeof(head));
	memset(edge, 0, sizeof(edge));
	memset(f, 0, sizeof(f));
	memset(vis, 0, sizeof(vis));
	tot = 0;
	for(register int i = 1; i <= n; i++) 
		for(register int j = 1; j <= m; j++)
			if(mat[i][j] <= x) addedge(i, j);
	int cnt = 0;
	for(register int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		cnt += dfs(i);
	}
	if(cnt > n - k) return 1;
	return 0;
}

int main() {
	n = get(), m = get(), k = get();
	for(register int i = 1; i <= n; i++) 
		for(register int j = 1; j <= m; j++) 
			mat[i][j] = get(), bin[++top] = mat[i][j];
	sort(bin + 1, bin + 1 + top);
	l = 1, r = top;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(chk(bin[mid])) ans = bin[mid], r = mid - 1;
		else l = mid + 1;
	}
	cout << ans << endl; 
	return 0;
}

这种写法与第一种的不同之处仅有一处：

在 chk() 函数中，前者建的是从 i 到 j + n的双向边，而后者建的是 i 到 j 的单向边。

我认为第二种写法是错误的，原因有二：

• 左右部分点没有分开编号
• 建的是单向边

然而这两种解法在我校 OJ、Luogu、Loj 上均可以 AC，在本机上对拍了 1839 组数据没有出现错误。

那么，这种写法到底正确与否？若正确，为什么？若错误，如何构造 Hack 数据？

感谢大佬们解答（