AcWing 2735. 舞会(匈牙利算法)/(反向求答)
原题链接
困难
作者:
殇ベ_11
,
2021-05-22 12:18:31
,
所有人可见
,
阅读 289
题目描述
某学校要召开一个舞会。
现在已知在学校的所有 n 名学生中,有些学生曾经互相跳过舞。(跳过舞的两个学生一定是一个男生和一个女生。)
现在要求被邀请的学生中的任何一对男生女生互相都不能跳过舞,求这个舞会最多能够邀请多少学生参加。
输入格式
输入的第一行是 n 和 m。其中 n 是可选的学生的总数,m 是已知的跳过舞的学生的对数。
然后有 m 行,分别包含两个非负整数,表示这两个编号的学生曾经跳过舞。其中,学生的编号从 0 号到 n−1 号。
输出格式
只要求输出一行,其中包含一个数字,即能够邀请的最大的学生数。
数据范围
1≤n≤1000,
1≤m≤2000
样例
输入样例1:
8 6
0 2
2 3
3 5
1 4
1 6
3 1
输出样例1:
5
输入样例2:
20 5
5 2
4 3
18 17
0 11
13 3
输出样例2:
16
算法1
C++ 代码
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e4;
int n,m;
int head[N],idx = 0;
int match[N];
bool vis[N];
int res;
struct edge{
int to;
int next;
}e[N];
void add(int u,int v)
{
e[++idx].to = v;
e[idx].next = head[u];
head[u] = idx;
}
int find(int u)
{
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if(!vis[v])
{
vis[v] = true;
if(!match[v] || find(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i ++)
{
int u, v;
scanf("%d%d",&u,&v);
add(u + 1,v + 1);
}
for(int i = 1;i <= n ;i ++){
memset(vis, false, sizeof(vis));
if(find(i)) res ++;
}
printf("%d",n - res);
return 0;
}
# hack
# input
# output