记录编号	37581	评测结果	AAAAAAAAAA
题目名称	[SDOI 2007] 环球旅行问题	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2012-04-03 11:44:48	内存使用	0.28 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
const int MAX=1002;
const int PV=500;
int Used[MAX],Mat[MAX];
vector<int> Map[MAX];
int N,M;

inline void init()
{
	scanf("%d %d\n",&N,&M);
	int a,b;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d\n",&a,&b);
		a++,b++;
		Map[a].push_back(b+PV);
		Map[b+PV].push_back(a);
	}
}

bool cross(int k)
{
	int v;
	for(unsigned int i=0;i<Map[k].size();i++)
	{
		v=Map[k][i];
		if(Used[v]) continue;
		Used[v]=1;
		if(!Mat[v] || cross(Mat[v]))
		{
			Mat[v]=k;
			return true;
		}
	}
	return false;
}

inline void hungary()
{
	int Ans=N;
	for(int i=1;i<=N;i++)
	{
		memset(Used,0,sizeof(Used));
		Ans-=cross(i);
	}
	printf("%d\n",Ans);
}

int main() 
{
	freopen("chbtrip.in","r",stdin);
	freopen("chbtrip.out","w",stdout);
	init();
	hungary();
	return 0;
}