题目描述
某学校要召开一个舞会。已知学校所有 (n) 名学生中，有些学生曾经互相跳过舞。当然跳过舞的学生一定是一个男生和一个女生。在这个舞会上，要求被邀请的学生中的任何一对男生和女生互相都不能跳过舞。求这个舞会最多能邀请多少个学生参加。
首先呢，这道题是一道典型的二分图最大独立集问题。
我们把每对跳过舞的同学连一条边，那么我们所选出来的同学中就不能有连边。
这正好符合二分图最大独立集的概念，包含点数最多的，且任意两点之间没有连边的最大集。
我们先证明一下，为什么我们这样建边会得到一张二分图。
我们可以把男女分在左右两边，题目保证了跳过舞的人都是男女配对的，所以男男之间不会有连边。
所以保证了同一个集合内没有连边，所以这是一个二分图。
再说了，要是有奇环的话，那么就会有一个人的性别不明确（不男不女？？？） 大雾。
自己画一下图就好理解了。
那么我们最终的答案就是二分图的最大独立集。
这东西怎么求呢？ 先来一个定理：
二分图最大独立集等于 n - 最小点覆盖 等于 n - 二分图最大匹配数。
第一个等式的话很好证出来。
我们选出来的点之间没有连边就等价于用最小的点覆盖所有的边，也就是我们所说的最小点覆盖问题。
至于为什么最小点覆盖等于最大匹配数，先记住一下吧，自己以后会把这个坑补上的。
当我们建完图后，你还会发现一个重要的问题就是，你找不到从从哪些点开始匹配，即找不到左边集合中的点。
我一般解决这个问题的方法就是先对整张图跑一边染色法，把所有标记为 (1) 的点扔到一个 (vector) 中，然后对这些点跑一边最大匹配就可以。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1010;
int n,m,u,v,ans,tot;
int head[N],match[N],c[N];
bool vis[N];
vector<int> q;
struct node
{
int to,net;
}e[100010];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
bool dfs(int x)
{
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(!vis[to])
{
vis[to] = 1;
if(!match[to] || dfs(match[to]))
{
match[to] = x;
return 1;
}
}
}
return 0;
}
void bfs(int x,int col)
{
c[x] = col;
if(c[x] == 1) q.push_back(x);
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(!c[to]) bfs(to,3-col);
}
}
int main()
{
n = read(); m = read();
for(int i = 1; i <= m; i++)
{
u = read()+1; v = read()+1;//记得学生编号是从零开始的，要加一个1转化为从1到n
add(u,v); add(v,u);
}
for(int i = 1; i <= n; i++)
{
if(!c[i]) bfs(i,1);//染色
}
for(int i = 0; i < q.size(); i++)//匈牙利算法
{
memset(vis,0,sizeof(vis));
int x = q[i];
if(dfs(x)) ans++;
}
printf("%d
",n-ans);
return 0;
}