本文主要是介绍UVA 12083 - Guardian of Decency(二分图最大匹配），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 12083 - Guardian of Decency
题目链接
题意：给定一些男女，满足身高差不大于40，喜欢同一种音乐，不喜欢同一种体育项目，并且性别不同，就可能发生关系，现在老师要带一些男女出去玩，要求不能有一对发生关系，问最多能带多少人
思路：分男女，把会发生关系的连边，然后做最大匹配，最后n-最大匹配就是最多能带的人
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdlib>
using namespace std;const int N = 505;struct People {int h;string music, sport;People() {}People(int h, string music, string sport) {this->h = h;this->music = music;this->sport = sport;}
}boy[N], girl[N];vector<int> g[N];int bn, gn;int T, n;bool judge(People a, People b) {if (abs(a.h - b.h) <= 40 && a.music == b.music && a.sport != b.sport) return true;return false;
}int match[N], vis[N];bool dfs(int u) {for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (vis[v]) continue;vis[v] = 1;if (match[v] == -1 || dfs(match[v])) {match[v] = u;return true;}}return false;
}int hungary() {int ans = 0;memset(match, -1, sizeof(match));for (int i = 0; i < bn; i++) {memset(vis, 0, sizeof(vis));if (dfs(i)) ans++;}return ans;
}int main() {cin >> T;while (T--) {cin >> n;int h; bn = gn = 0;string sex, music, sport;for (int i = 0; i < n; i++) {cin >> h >> sex >> music >> sport;if (sex == "M") boy[bn++] = People(h, music, sport);else girl[gn++] = People(h, music, sport);}for (int i = 0; i < bn; i++) {g[i].clear();for (int j = 0; j < gn; j++) {if (judge(boy[i], girl[j]))g[i].push_back(j);}}printf("%d\n", n - hungary());}return 0;
}这篇关于UVA 12083 - Guardian of Decency(二分图最大匹配）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
