题解 P6268 【[SHOI2002]舞会】

· · 题解

这题是我做的第三道二分图最大匹配的题目。前两道都是纯模板。

在做这道题的时候我还不知道二分图的最大独立集与最大匹配的关系，甚至没发现这题是在求最大独立集。。。

所以我推答案花了一点时间，下面给出我的思路：

首先很显然我们只需要考虑跳过舞的学生，其他学生一定都可以参加舞会。

如果在每一对跳过舞的学生之间连一条无向边，那么一定会构成一张二分图。

注意这里是无向边，因为你此时并不知道这两个人哪个是男哪个是女 安能辨我是雄雌。

那么求出有多少人不能参加舞会会比较简单。

不难发现这个人数其实就是这张二分图的最大匹配，因为如果排除了这些在最大匹配中的人，其他人就一定都能选；而如果不排除，则至少会有一对跳过舞的人还被保留。

那么在最大匹配的点集之外的点都是可以选的。

所以我们需要求的答案就是 n\ - 最大匹配的边数。

关于求最大匹配，我们可以使用匈牙利算法，在这里就不再介绍了。

不过还有一个问题，如果在匈牙利算法中直接枚举所有点的话是不行的 连样例都过不了。

所以我们需要先对二分图进行染色，找出其中是同一性别的人不管是男是女，然后跑一遍匈牙利算法就可以愉快地 AC 了。

话说是不是只有我喜欢大括号换行

#include <cstdio>
#include <iostream>

using namespace std;

const int MAXN = 1010;

int n, m, g[MAXN][MAXN], now[MAXN], col[MAXN];
bool vis[MAXN];

//二分图染色，找出同一性别的人
void color(int u, int pre, int c)
{
    col[u] = c;
    for(int i=1;i<=n;i++)
        if(g[u][i] && !col[i])
            color(i, u, 3 - c);
}

bool find(int u)
{
    for(int i=1;i<=n;i++)
        if(g[u][i] && !vis[i])
        {
            vis[i] = 1;
            if(!now[i]|| find(now[i]))
            {
                now[i] = u;
                return 1;
            }
        }
    return 0;
}

inline int match()
{
    int res = 0;
    for(int i=1;i<=n;i++)
    {
        if(col[i] != 1) continue;
        //只选取某一性别的人
        for(int j=1;j<=n;j++)
            vis[j] = 0;
        res += find(i);
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        ++x; ++y; //处于个人习惯，这里把所有点+1
        g[x][y] = g[y][x] = 1;
    }
    for(int i=1;i<=n;i++)//给每一个人染色
    //对于不在二分图中的点是无所谓的
        if(!col[i]) color(i, 0, 1);
    printf("%d\n",n - match());
    return 0;
}