记录编号	431298	评测结果	AAAAAAAAAA
题目名称	血帆海盗	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.322 s
提交时间	2017-07-31 15:54:49	内存使用	2.91 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 100005
#define maxx 400005
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{	char c=getchar();int x=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
struct road{int en,cap,nex;}ro[maxx];
int ans,mk,n,m,num,hea[maxn],tail,sta[maxn],bel[maxn],sum,dis[maxn],low[maxn],dfn[maxn],inf=0xfffffff,st,ed;
bool inst[maxn];
void add(int x,int y,int z)
{	ro[num].en=y;ro[num].cap=z;ro[num].nex=hea[x];hea[x]=num++;
	ro[num].en=x;ro[num].cap=0;ro[num].nex=hea[y];hea[y]=num++;
}
void tarjan(int x)
{	low[x]=dfn[x]=++mk;
	sta[++tail]=x;inst[x]=1;
	for(int i=hea[x];i!=-1;i=ro[i].nex)
	{	if(!ro[i].cap) continue;
		int v=ro[i].en;
		if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
		else if(inst[v]) low[x]=min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x])
	{	int u;sum++;
		while(1)
		{	u=sta[tail--];inst[u]=0;
			bel[u]=sum;
			if(u==x) break;
		}
	}
}
bool bfs(int s,int t)
{	queue<int>q;mem(dis,0);
	q.push(s);dis[s]=1;
	while(!q.empty())
	{	int u=q.front();q.pop();
		for(int i=hea[u];i!=-1;i=ro[i].nex)
		{	int v=ro[i].en;
			if(!dis[v]&&ro[i].cap){dis[v]=dis[u]+1;q.push(v);if(v==t) return 1;}
		}
	}
	return 0;
}
int dfs(int x,int y,int z)
{	if(x==y) return z;
	int f,tmp=0;
	for(int i=hea[x];i!=-1;i=ro[i].nex)
	{	int v=ro[i].en;
		if((dis[v]==dis[x]+1)&&ro[i].cap)
		{	f=dfs(v,y,min(z-tmp,ro[i].cap));
			if(!f){dis[v]=0;continue;}
			ro[i].cap-=f;ro[i^1].cap+=f;tmp+=f;
			if(tmp==z) return tmp;
		}
	}
	return tmp;
}
void dinic(int s,int t){while(bfs(s,t)) ans+=dfs(s,t,inf);}
int fff()
{	freopen("bloodsail.in","r",stdin);
	freopen("bloodsail.out","w",stdout);
	mem(hea,-1);int x,y,edge;
	n=read();m=read();edge=n>>1;ed=n+1;
	for(int i=1;i<=edge;i++) add(st,i,1),add(i+edge,ed,1);
	for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y,1);
	dinic(st,ed);
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=edge;i++)
		for(int j=hea[i];j!=-1;j=ro[j].nex)
			if(!ro[j].cap&&bel[ro[j].en]==bel[i]&&ro[j].en) ans--;
	printf("%d",ans);
	return 0;
}
int ttt=fff();
int main(){;}