HDU2444 【二分图判定+最大匹配】

套模板很好的题？

#include<bits/stdc++.h>
using namespace std; 

const int N=2e2+10;
const int M=4e4+10;

struct asd{
	int to;
	int next;
};
asd q[M];
int head[M],tol;
int n,m;
int col[N];

void add(int u,int v)
{
	q[tol].to=v;
	q[tol].next=head[u];
	head[u]=tol++;
}

void init()
{
	tol=0;
	memset(head,-1,sizeof(head));
	
}

int cy[N];
bool vis[N];
bool Find(int u)
{
	for(int i=head[u];i!=-1;i=q[i].next)
	{
		int v=q[i].to;
		if(!vis[v])
		{
			vis[v]=1;
			if(cy[v]==-1||Find(cy[v]))
			{
				cy[v]=u;
				return true;
			}
		}
	}
	return false;
}

bool Judge(int s)
{
	queue<int>que;
	col[s]=0;
	que.push(s);
	while(!que.empty())
	{
		int u=que.front();que.pop();
		for(int i=head[u];i!=-1;i=q[i].next)
		{
			int v=q[i].to;
			if(col[v]==-1)
			{
				col[v]=1-col[u];
				que.push(v);
			}
			else{
				if(col[v]==col[u])
					return false;
			}
		}
	}
	return true;
}

int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		int u,v;
		init();
		while(m--)
		{
			scanf("%d%d",&u,&v);
			add(u,v);
			add(v,u);
		}
		
		int flag=1;
		memset(col,-1,sizeof(col));
		for(int i=1;i<=n;i++)
		{
			if(col[i]==-1)
			{
				if(!Judge(i))
				{
					flag=0;
					break;
				}
			}
		}
		
		if(!flag){
			puts("No");
			continue;
		}
		
		int ans=0;
		memset(cy,-1,sizeof(cy));
		for(int i=1;i<=n;i++)
		{
			memset(vis,0,sizeof(vis));
			if(Find(i))
				ans++;	
		}
		printf("%d
",ans>>1);
	}
	return 0;
}