爆零求调
查看原帖
爆零求调
683212
Henly_Z楼主2023/11/24 21:32
#include<bits/stdc++.h>
using namespace std;
int n , m , k,a[2005][2005],l,r=0,mapx[255][255],cnt,c[300],v[300];
void build(int mid){
	memset(mapx,0,sizeof(mapx));
	memset(c,0,sizeof(c));
	cnt = 0;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= n ; j++){
			if(a[i][j] <= mid){
				mapx[i][j+n] = 1;
			}
		}
	}
}
int dfs(int x)
{
	for (int i = 1; i <= n; i++)
	{
		if (v[i] != 1 && mapx[x][i])
		{
			v[i] = 1;
			if (!c[i] || dfs(c[i]))
			{
				c[i] = x;
				return 1;
			}
		}
	}
	return 0;
}
bool solve(){
	int x = 0;
	for(int i = 1 ; i <= n ; i++){
		memset(v,0,sizeof(v));
		if(dfs(i)) x++; 
	}
	if(x > n - k) return true;
	return false;
}
int main(){
//	freopen("matrix.in","r",stdin);
//	freopen("matrix.out","w",stdout);
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			cin >> a[i][j];
			r = max(a[i][j],r);
		}
	}
	int answer1 = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		build(mid);
		if(solve()){
			answer1 = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	cout <<answer1;
} 
2023/11/24 21:32
加载中...