当前位置： 移动技术网 > 移动技术>移动开发>IOS > O - Steady Cow Assignment POJ - 3189（二分 + 多重匹配）

O - Steady Cow Assignment POJ - 3189（二分 + 多重匹配）

2020年07月13日  | 移动技术网移动技术  | 我要评论

解题思路：

  • 将每头牛对牛棚满意度依次存储
  • 二分区间（区间最大为B）
  • 枚举区间头，从而确定区间尾
  • 进行多重匹配的边必须要先满足在区间内

AC代码：

// Test1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1010;
int N, B;
int rk[maxn][100], cap[maxn], vis[maxn];
int match[50][maxn];
void Init() {
	int x;
	cin >> N >> B;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= B; j++) {
			cin >> x;//第j个输入的牛棚是第j满意的
			rk[i][x] = j;
		}
	for (int i = 1; i <= B; i++)
		cin >> cap[i];
}
bool dfs(int x, int l, int r) {
	for (int i = 1; i <= B; i++) {
		if (l <= rk[x][i] && rk[x][i] <= r && !vis[i]) {//一定要满足在这个区间内
		//其实可以借鉴如果要二分，那么不需要重新建边，要先满足在某个范围内
			vis[i] = 1;
			if (match[i][0] < cap[i]) {
				match[i][++match[i][0]] = x;
				return true;
			}
			for (int j = 1; j <= match[i][0]; j++) 
				if (dfs(match[i][j], l, r)) {
					match[i][j] = x;
					return true;
				}
		}
	}
	return false;
}
bool Maxmatch(int l, int r) {
	int sum = 0;
	memset(match, 0, sizeof(match));
	for (int i = 1; i <= N; i++) {
		memset(vis, 0, sizeof(vis));
		if (!dfs(i, l, r)) return false;
	}
	return true;
}
bool check(int mid) {
	for (int i = 1; i <= B; i++)
		if (Maxmatch(i, i + mid))
			return true;
	return false;
}
void Solve() {
	int lef = 0, rig = B, mid = (lef + rig) >> 1, ans;
	while (lef <= rig) {
		if (check(mid)) rig = mid - 1, ans = mid;
		else lef = mid + 1;
		mid = (lef + rig) >> 1;
	}
	cout << ans + 1 << endl;//题目要求
}
int main() {
	Init();
	Solve();
	return 0;
}

ps：其实可以借鉴，如果要二分，那么不需要重新建边，先将边全部相连， 要先满足在某个范围内

本文地址：https://blog.csdn.net/weixin_45691711/article/details/107284640

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网