记录编号	9924	评测结果	AAAAAAAAAA
题目名称	[AHOI2006] 棋盘上的问题	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	19.147 s
提交时间	2009-04-22 19:29:45	内存使用	99.87 MiB

/* 
 * Problem: HAOI2009 模拟2 board
 * Author: Guo Jiabao
 * Time: 2009.4.22 18:59
 * State: Done
 * Memo: 最大匹配 网络流 贪心初始流
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=200004*2,MAXM=600001*2+MAXN*2,INF=0x7FFFFFFF;
using namespace std;
struct edge 
{
	edge *next,*op;
	int t,c;
	bool original;
}ES[MAXM],*V[MAXN],*P[MAXN],*Stae[MAXN],*brink[MAXN];
int N,M,S,T,EC,Ans1,Ans2,Ans;
int Stap[MAXN],Stop,Lv[MAXN],Bel[MAXN],DFN[MAXN],Low[MAXN],Dindex,Bcnt;
int C[MAXN],Order[MAXN],Deg[MAXN];
bool instack[MAXN],used[MAXN];
void tarjan(int i)
{
	int j;
	DFN[i]=Low[i]=++Dindex;
	Stap[++Stop]=i;
	instack[i]=true;
	for (edge *e=V[i];e;e=e->next)
	{
		j=e->t;
		if (!e->c) continue;
		if (!DFN[j])
		{
			tarjan(j);
			if (Low[j]<Low[i])
				Low[i]=Low[j];
		}
		else if (instack[j] && DFN[j]<Low[i])
			Low[i]=DFN[j];
	}
	if (Low[i]==DFN[i])
	{
		++Bcnt;
		do{
			j=Stap[Stop--];
			instack[j]=false;
			Bel[j]=Bcnt;
		}while (i!=j);
	}
}
void scc()
{
	Dindex=Stop=Bcnt=0;
	for (int i=S;i<=T;i++)
		if (!Bel[i])
			tarjan(i);
}
bool Dinic_BFS()
{
	int i,j,head=0,tail=-1;
	memset(Lv,-1,sizeof(Lv));
	Lv[Stap[++tail]=S]=0;
	while (head<=tail)
	{
		i=Stap[head++];
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (e->c && Lv[j]==-1)
			{
				Lv[j]=Lv[i]+1;
				Stap[++tail]=j;
				if (j==T)
					return true;
			}
		}
	}
	return false;
}
void Dinic_Augment()
{
	int i,j,delta;
	for (i=S;i<=T;i++)
		P[i]=V[i];
	Stap[Stop=1]=S;
	while (Stop)
	{
		i=Stap[Stop];
		if (i!=T)
		{
			for (;P[i];P[i]=P[i]->next)
				if (P[i]->c && Lv[i]+1==Lv[j=P[i]->t])
					break;
			if (P[i])
			{
				Stap[++Stop]=j;
				Stae[Stop]=P[i];
			}
			else
			{
				Stop--;
				Lv[i]=-1;
			}
		}
		else
		{
			delta=INF;
			for (i=Stop;i>=2;i--)
				if (Stae[i]->c < delta)
					delta = Stae[i]->c;
			for (i=Stop;i>=2;i--)
			{
				Stae[i]->c -= delta;
				Stae[i]->op->c +=delta;
				if (Stae[i]->c == 0)
					Stop=i-1;
			}
		}
	}
}
void Dinic()
{
	while (Dinic_BFS())
		Dinic_Augment();
}
void countingsort()
{
	int i;
	for (i=1;i<=N;i++)
		C[ Deg[i] ]++;
	for (i=1;i<=N;i++)
		C[i]+=C[i-1];
	for (i=N;i>=1;i--)
		Order[ C[Deg[i]]-- ]=i;
}
void initialflow()
{
	int i,j,a,b,Mini;
	edge *e,*f;
	used[S]=true;
	countingsort();
	for (i=1;i<=N;i++)
	{
		a=Order[i];
		Mini=b=INF;
		for (e=V[a];e;e=e->next)
		{
			j=e->t;
			if (!used[j] && Deg[j]<Mini)
			{
				Mini=Deg[j];
				b=j;
				f=e;
			}
		}
		if (b!=INF)
		{
			brink[a]->c = f->c = brink[b]->c = 0;
			brink[a]->op->c = f->op->c = brink[b]->op->c = 1;
			used[b]=true;
		}
	}
}
inline void addedge(int a,int b,int c,bool o)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=0;
	V[a]->op=V[b]; V[b]->op=V[a];
	if (o)
	{
		V[a]->original=true;
		Deg[a]++;
		Deg[b]++;
	}
	else
	{
		if (a==S)
			brink[b]=V[a];
		else
			brink[a]=V[a];
	}
}
void init()
{
	int i,a,b;
	freopen("board.in","r",stdin);
	freopen("board.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		addedge(a,b+N,1,true);
	}
	S=0;T=N+N+1;
	for (i=1;i<=N;i++)
	{
		addedge(S,i,1,false);
		addedge(i+N,T,1,false);
	}
}
void findnp()
{
	for (int i=1;i<=N;i++)
	{
		for (edge *e=V[i];e;e=e->next)
		{
			if (e->original && e->c==1)
				Ans1++;
		}
	}
}
void circle()
{
	for (int i=1;i<=N;i++)
	{
		for (edge *e=V[i];e;e=e->next)
		{
			if (e->op->c==1 && e->original && Bel[i]==Bel[e->t])
				Ans2++;
		}
	}
}
void solve()
{
	initialflow();
	Dinic();
	findnp();
	scc();
	circle();
	Ans=Ans1+Ans2;
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}