题意

已知班级有g个女孩和b个男孩，所有女生之间都相互认识，所有男生之间也相互认识，给出m对关系表示哪个女孩与哪个男孩认识。现在要选择一些学生来组成一个集合，使得里面所有人都认识，求此集合最大人数。

思路

二分图的最大团的定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。

原图的最大团 = 补图的最大独立集

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 211;

int mp[N][N], match[N], vis[N], n, m;

bool dfs(int u) {

    for(int v = 1; v <= m; v++) {

        if(vis[v] || !mp[u][v]) continue;

        vis[v] = 1;

        if(match[v] == -1 || dfs(match[v])) {

            match[v] = u;

            return true;

        }

    } return false;

}

int Hungry() {

    memset(match, -1, sizeof(match));

    int ans = 0;

    for(int i = 1; i <= n; i++) {

        memset(vis, 0, sizeof(vis));

        ans += dfs(i);

    } return n + m - ans;

}

int main() {

    int e, cas = 1;

    while(~scanf("%d%d%d", &n, &m, &e), n + m + e) {

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= m; j++) mp[i][j] = 1;

        for(int i = 1; i <= e; i++) {

            int u, v; scanf("%d%d", &u, &v);

            mp[u][v] = 0;

        }

        printf("Case %d: %d\n", cas++, Hungry());

    }

    return 0;

}

巴特西

POJ 3692：Kindergarten（二分图最大团）

题意

思路

最新文章

热门文章