[SHOI2002]舞会

Descriptio

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

Input

第一行为N，M代表有N个学生，M是已跳过舞的学生的对数N<=1000,M<=2000.接下来M行，每行两个非负整数，表示这两个学生曾跳过舞。学生的编号从0到N-1号

Output

输出一个数字，如题所示.

Sample Input

20 12

5 15

16 12

16 14

13 9

6 12

16 3

1 7

17 18

5 3

5 18

19 10

8 0

Sample Output

12

二分图最大独立点集，假定最大匹配数为\(K\)，总点数为\(N\)，那么就还剩\(N-2*K\)个点独立，又因为在\(K\)个匹配中，必能选出\(K\)个点和其他\(N-2*K\)个点都不相连，因此答案就为\(N-K\)

有一点需要注意，男女生的顺序需要定好，决定好是由男生匹配女生还是反着匹配，不过本题已经规定了后面的读入先男后女，因此不需要决定顺序

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())  x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)	 print(x/10);

	putchar(x%10+'0');

}

const int N=1e3,M=2e3;

int pre[M+10],now[M+10],child[M+10];

int path[N+10];

bool use[N+10];

int n,m,tot,ans;

void join(int x,int y){pre[++tot]=now[x],now[x]=tot,child[tot]=y;}

bool check(int x){

	for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

		if (use[son])   continue;

		use[son]=1;

		if (path[son]<0||check(path[son])){

			path[son]=x;

			return 1;

		}

	}

	return 0;

}

int main(){

	n=read(),m=read();

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

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

		int x=read(),y=read();

		join(x+1,y+1);

	}

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

		memset(use,0,sizeof(use));

		if (check(i))   ans++;

	}

	printf("%d\n",n-ans);

	return 0;

}

巴特西

[SHOI2002]舞会

最新文章

热门文章