10分求助
查看原帖
10分求助
362472
灵霄楼主2023/1/17 16:15

4个WA 5个RE

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 255;
int n, m, k;
int head[N * 2], ver[N * N], Next[N * N], w[N * N], tot;
int max_v, res, mid;
int match[N * 2], vis[N * 2];
void add(int x, int y, int val){
	ver[++tot] = y;
	Next[tot] = head[x];
	head[x] = tot;
	w[tot] = val;
}
bool path(int x){
	for (int i = head[x]; i; i = Next[i]){
		int y = ver[i];
		if (!vis[y] && w[i] <= mid){
			vis[y] = 1;
			if(path(match[y]) || match[y] == -1){
				match[y] = x;
				return true;
			}
		}
	} 	
	return false;
}
int maxMatch(){
	res = 0;
	memset(match, -1, sizeof(match));
	for (int i = 1; i <= n; i++){
		memset(vis, 0, sizeof(vis));
		if (path(i))
			res ++;
	}
	return res;
}
int v;
int main(){
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> v;
			max_v = max(v, max_v);
			add(i, j, v);
			add(j, i, v);
		}
	}
	int l = 0, r = max_v;
	while (l < r){
		mid = l + r >> 1;
		if (maxMatch() > n - k)
			r = mid;
		else	
			l = mid + 1;
	}
	cout << l << endl;
	return 0;
}
2023/1/17 16:15
加载中...