记录编号	158756	评测结果	AAAAAAAAAA
题目名称	血帆海盗	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	1.644 s
提交时间	2015-04-17 13:58:14	内存使用	17.77 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
 
#define N 300010
#define INF 0x3f3f3f3f
 
using namespace std;
 
struct edge{
	int x,to,cap;
}E[N<<1],R[N];
 
int g[N],n,m,totE=1,S,T,h[N],ans,cnt;
int cur[N],dfsn[N],low[N],tott,belong[N];
bool v[N];
 
void ade(int x,int y){
	E[++totE]=(edge){y,g[x],1}; g[x]=totE;
	E[++totE]=(edge){x,g[y],0}; g[y]=totE;
}
 
queue<int> q;
 
bool bfs(){
	#define p E[i].x
	memset(v,0,sizeof(v));
	q.push(S); v[S]=h[S]=1;
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(int i=g[x];i;i=E[i].to)
			if(!v[p] & E[i].cap){
				h[p]=h[x]+1; v[p]=1; q.push(p);
			}
	}
	return v[T];
}
 
int dinic(int x,int flow){
	#define p E[i].x
	if(x==T||!flow) return flow;
	int f=0;
	for(int i=g[x];i;i=E[i].to){
		if(h[p]!=h[x]+1||!E[i].cap) continue;
		int tp=dinic(p,min(flow,E[i].cap));
		flow-=tp; f+=tp;
		E[i].cap-=tp; E[i^1].cap+=tp;
		if(!flow) break;
	}
	if(!f) h[x]=-1; return f;
}
 
void buildgraph(){
	S=n+1; T=n+2;
	for(int i=1;i<=(n>>1);i++) ade(S,i),ade(i+(n>>1),T);
	for(int i=1;i<=m;i++) ade(R[i].x,R[i].to);
	while(bfs()) ans+=dinic(S,INF);
}

stack<int> st;

void dfs(int x){
	#define p E[i].x
	dfsn[x]=low[x]=++tott;
	st.push(x); v[x]=1;
	for(int i=g[x];i;i=E[i].to){
		if(!E[i].cap) continue;
		if(!dfsn[p]){
			dfs(p);
			low[x]=min(low[x],low[p]);
		}
		else if(!belong[p]){
			low[x]=min(low[x],dfsn[p]);
		}
	}
	if(low[x]==dfsn[x]){
		cnt++;
		while(1){
			int t=st.top(); st.pop();
			belong[t]=cnt;
			if(t==x) break;
		}
	}
}

int main(){
	freopen("bloodsail.in","r",stdin);
	freopen("bloodsail.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&R[i].x,&R[i].to);
	buildgraph();
	memset(v,0,sizeof(v));
	for(int i=1;i<=n;i++) if(!dfsn[i]) dfs(i);
	#define p E[i].x
	for(int x=1;x<=(n>>1);x++){
		for(int i=g[x];i;i=E[i].to){
			if(E[i].cap||p==S) continue;
			if(belong[p]==belong[x]) ans--;
		}
	}
	printf("%d\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}