UVA - 12083 Guardian of Decency （二分匹配）

题意：有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;

}

巴特西

UVA - 12083 Guardian of Decency （二分匹配）

最新文章

热门文章