C++11(clang++ 3.9) 解法, 执行用时: 87ms, 内存消耗: 492K, 提交时间: 2019-05-12 16:56:21

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 1000;
int w[maxn], sw[maxn], f[maxn];
vector<int> G[maxn];
bool b[maxn];
bool find(int u){
	for(int v : G[u]) if(not b[v]){
		b[v] = true;
		if(f[v] == - 1 or find(f[v]))return f[v] = u, true;
	}
	return false; 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	for(cin >> T; T; T -= 1){
		int n, m, k;
		cin >> n >> m >> k;
		for(int i = 0; i < n * m; i += 1){
			cin >> w[i];
			sw[i] = w[i];
		}
		sort(sw, sw + n * m);
		int L = 0, R = n * m;
		while(L + 1 < R){
			int M = sw[(L + R) >> 1], ans = 0;
			for(int i = 0; i < n * m; i += 1){
				G[i].clear();
				if(w[i] >= M) ans += 1;
				f[i] = -1;
			}
			for(int i = 0; i < n; i += 1)
				for(int j = 0; j < m; j += 1)
					if((i + j) % 2 == 0 and w[i * m + j] >= M){
						if(i > 0 and w[(i - 1) * m + j] >= M) G[i * m + j].push_back((i - 1) * m + j);
						if(i + 1 < n and w[(i + 1) * m + j] >= M) G[i * m + j].push_back((i + 1) * m + j);
						if(j > 0 and w[i * m + j - 1] >= M) G[i * m + j].push_back(i * m + j - 1);
						if(j + 1 < m and w[i * m + j + 1] >= M) G[i * m + j].push_back(i * m + j + 1);
					}
			for(int i = 0; i < n; i += 1)
				for(int j = 0; j < m; j += 1)
					if((i + j) % 2 == 0 and w[i * m + j] >= M){
						fill(b, b + n * m, false);
						if(find(i * m + j)) ans -= 1;
					}
			if(ans >= k) L = (L + R) >> 1;
			else R = (L + R) >> 1;
		}
		cout << sw[L] << "\n";
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 76ms, 内存消耗: 612K, 提交时间: 2019-05-15 20:30:35

#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 1e3+9;
int n, m;
vector<int>e[maxn];
int f[maxn], a[maxn][maxn];
bool b[maxn];
int dx[]={0, 0, -1, 1};
int dy[]={-1, 1, 0, 0};
bool find(int u){
	for(int i=0; i<e[u].size(); ++i){
		int v=e[u][i];
		if(b[v]){
			continue;
		} 
		b[v]=true;
		if(-1==f[v]||find(f[v])){
			f[v]=u;
			return true;
		}
	}
	return false;
}
bool is_in(int x, int y){
	return 0<=x&&x<n&&0<=y&&y<m;
}
bool ok(int mid, int need){
	for(int i=0; i<n*m; ++i){
		e[i].clear();
		f[i]=-1;
	}
	int ans=0;
	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			if(a[i][j]>=mid){
				++ans;
			}
			if(a[i][j]>=mid&&(i+j)%2){
				int cd=i*m+j;
				for(int k=0; k<4; ++k){
					int nx=i+dx[k], ny=j+dy[k];
					if(is_in(nx, ny)&&a[nx][ny]>=mid){
						e[cd].push_back(nx*m+ny);
					}
				}
			}
		}
	}
	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			if(a[i][j]>=mid&&(i+j)%2){
				for(int k=0; k<n*m; ++k){
					b[k]=false;
				}
				if(find(i*m+j)){
					--ans;
				}
			}
		}
	}
	return ans>=need;
}
void solve(){
	int k;
	scanf("%d%d%d", &n, &m, &k);
	int L=1009, R=0;
	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			scanf("%d", &a[i][j]);
			L=min(L, a[i][j]);
			R=max(R, a[i][j]);
		}
	}
	while(L<R){
		int mid=(L+R+1)/2;
		if(ok(mid, k)){
			L=mid;
		}
		else{
			R=mid-1;
		}
	}
	printf("%d\n", L);
	
}
int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		solve();
	}
	return 0;
}