[SHOI2002]舞会

题目描述

某学校要召开一个舞会。已知学校所有 $n$ 名学生中，有些学生曾经互相跳过舞。当然跳过舞的学生一定是一个男生和一个女生。在这个舞会上，要求被邀请的学生中的任何一对男生和女生互相都不能跳过舞。求这个舞会最多能邀请多少个学生参加。

输入格式

输入的第一行是 $n$ 和 $m$ 。其中 $n$ 是可选的学生的总数， $m$ 是已知跳过舞的学生的对数 ( $\leq 1000$ ， $\leq 2000$ ）。

然后有 $m$ 行，每行包括两个非负整数，表示这两个编号的学生曾经跳过舞。学生的编号从 $0$ 号到 $n - 1$ 号。

输出格式

输出文件仅一行，为一个数字，即能够邀请的最多的学生数。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

1、 二分图最大独立集的大小 = n - 最大匹配数
2、 我们可以考虑将这些跳过舞的人构建二分图，并通过匈牙利算法求出匹配对数。 而在二分图中一对匹配对应的是两个人，我们用总人数减去已参与匹配的人数
3、 由于配对会重复（即会出现match[a]=b,match[b]=a的情况），所以注意最后输出的是n-(ans/2)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 1e6 + 10;
int mp[N][N];
int n, m;
int head[N], ver[M], Next[M];
int tot;
bool vis[N];
int match[N];void add(int x, int y)
{ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}bool dfs(int x)
{for(int i = head[x], y; i; i = Next[i]){y = ver[i];if(!vis[y]){vis[y] = true;if(!match[y] || dfs(match[y])){match[y] = x;return true;}}}return false;
}int main()
{scanf("%d%d", &n, &m);int x, y;while(m--){scanf("%d%d", &x, &y);if(x > y) swap(x, y);mp[x + 1][y + 1] = 1;}for(int i = 1; i <= n; ++i){for(int j = i + 1; j <= n; ++j){if(mp[i][j]){add(i, j); add(j, i);		}}}int ans = 0;for(int i = 1; i <= n; ++i){memset(vis, false, sizeof vis);if(dfs(i)){++ans;	}}printf("%d\n", n - ans / 2);return 0;
}