題意：有N個人，已知身高、性別、音樂、運動。要求選出盡可能多的人，使這些人兩兩之間至少滿足下列四個條件之一。

1、身高差>40 ?2、性別相同 ?3、音樂不同 ?4、運動相同

分析：

1、很顯然性別相同的人一定能一起去，問題就在于如何在這些性別相同的人中加入性別不同的人。

2、把男女分開，進行二分匹配。

如果某個男生A與任何一個女生都滿足條件1、3、4之一，那這個男生就可以和這些女生一起選擇。

反之，如果按照男女之間不滿足條件1、3、4中的任何一個的原則連線，那么諸如男生A這樣的男生是不會與任何一個女生連線（匹配），即這樣的男生是獨立的。

假設女生比男生多的話，則ans = 女生人數 + 獨立男 = 女生人數 + (男生人數 - 匹配男) = n - 最大匹配數

同理，若男生比女生多，ans = 男生人數 + 獨立女 = 男生人數 + (女生人數 - 匹配女) = n - 最大匹配數

3、結論：ans =?n - 最大匹配數

PS：還有一種比較“殘忍”的理解方式，隊友告訴我的~= =

1、上述四個條件滿足任何一個都不會產生感情，那么如果這四個條件都不滿足的話，那就會產生感情。

2、按照這個原則將能產生感情的人進行最大匹配，設最大匹配數為m，即最終湊出了m對情侶。

3、然后“狠心”將他們拆散，即這m對中每對趕走一個人，那么剩下的n-m個人，一定兩兩湊不成情侶，即n-最大匹配數

#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define lowbit(x) (x & (-x)) const double eps = 1e-8; inline int dcmp(double a, double b){if(fabs(a - b) < eps) return 0;return a > b ? 1 : -1; } typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const int MAXN = 500 + 10; const int MAXT = 100 + 10; using namespace std; struct Node{int h;char sex[3];char music[MAXT];char sport[MAXT];void read(){scanf("%d%s%s%s", &h, sex, music, sport);} }num[MAXN]; int pic[MAXN][MAXN]; int match[MAXN]; bool used[MAXN]; int n; bool judge(int x, int y){return abs(num[x].h - num[y].h) > 40 || strcmp(num[x].music, num[y].music) != 0 || strcmp(num[x].sport, num[y].sport) == 0; } bool dfs(int x){for(int i = 0; i < n; ++i){if(num[i].sex[0] == 'F' && !used[i] && pic[x][i]){used[i] = true;if(match[i] == -1 || dfs(match[i])){match[i] = x;return true;}}}return false; } int hungary(){int cnt = 0;for(int i = 0; i < n; ++i){if(num[i].sex[0] == 'M' && dfs(i)){memset(used, false, sizeof used);++cnt;}}return cnt; } int main(){int T;scanf("%d", &T);while(T--){memset(pic, 0, sizeof pic);memset(match, -1, sizeof match);scanf("%d", &n);for(int i = 0; i < n; ++i){num[i].read();}for(int i = 0; i < n; ++i){if(num[i].sex[0] == 'F') continue;for(int j = 0; j < n; ++j){if(num[j].sex[0] == 'F' && !judge(i, j)){pic[i][j] = 1;//男連女，單向連線}}}printf("%d\n", n - hungary());}return 0; }

　　

轉載于:https://www.cnblogs.com/tyty-Somnuspoppy/p/7406096.html

總結

以上是生活随笔為你收集整理的UVA - 12083 Guardian of Decency （二分匹配）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。