记录编号	431100	评测结果	AAAAAAAAAA
题目名称	血帆海盗	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.420 s
提交时间	2017-07-31 09:25:19	内存使用	5.05 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
const int sj=100005;
int n,m,h[sj],e,a1,a2,mid,jg,dep[sj];
int ge,dfn[sj],low[sj],cnt,c[sj];
struct B
{
     int ne,v,w,u;
}b[sj*4];
bool r[sj];
void add(int x,int y,int z)
{
     b[e].v=y;
     b[e].w=z;
     b[e].u=x;
     b[e].ne=h[x];
     h[x]=e++;
}
void init()
{
     scanf("%d%d",&n,&m);
     memset(h,-1,sizeof(h));
     mid=n>>1;
     for(int i=1;i<=m;i++)
     {
        scanf("%d%d",&a1,&a2);
        add(a1,a2,1);
        add(a2,a1,0);
        r[a1]=1;
        r[a2]=1;
     }
     for(int i=1;i<=mid;i++)
       if(r[i])  add(0,i,1),add(i,0,0);
     for(int i=mid+1;i<=n;i++)
       if(r[i])  add(i,n+1,1),add(n+1,i,0);
     memset(r,0,sizeof(r));
}
queue<int> q;
int bfs(int x)
{
    memset(dep,0,sizeof(dep));
    dep[x]=1;
    while(!q.empty()) q.pop();
    q.push(x);
    while(!q.empty())
    {
       x=q.front();
       q.pop();
       for(int i=h[x];i!=-1;i=b[i].ne)
         if(!dep[b[i].v]&&b[i].w)
         {
           dep[b[i].v]=dep[x]+1;
           if(b[i].v==n+1) return 1;
           q.push(b[i].v);
         }
    }
    return 0;
}
int bj(int x,int y)
{
    return x<y?x:y;
}
int dfs(int u,int f)
{
    int ans=0;
    if(u==n+1) return f;
    for(int i=h[u],d;i!=-1;i=b[i].ne)
      if(b[i].w&&dep[b[i].v]>dep[u])
      {
         d=dfs(b[i].v,bj(f,b[i].w));
         f-=d;
         ans+=d;
         b[i].w-=d;
         b[i^1].w+=d;
         if(!f) break;
      }
    if(!ans) dep[u]=-1;
    return ans;
}
stack<int> p;
int tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    p.push(x);
    r[x]=1;
    for(int i=h[x];i!=-1;i=b[i].ne)
    {
       if(!b[i].w) continue;
       if(!dfn[b[i].v])
       {
         tarjan(b[i].v);
         low[x]=bj(low[x],low[b[i].v]);
       }
       else if(r[b[i].v]) 
         low[x]=bj(low[x],dfn[b[i].v]);
    }
    if(dfn[x]==low[x])
    {
       int ww;
       ge++;
       do
       {
          ww=p.top();
          p.pop();
          r[ww]=0;
          c[ww]=ge;
       }while(ww!=x);
    }
}
int main()
{
    //freopen("t.txt","r",stdin);
    freopen("bloodsail.in","r",stdin);
    freopen("bloodsail.out","w",stdout);
    init();
    while(bfs(0)) jg+=dfs(0,0x3fff);
    memset(r,0,sizeof(r));
    for(int i=1;i<=n;i++)
      if(!dfn[i])  tarjan(i);
    for(int i=1;i<=mid;i++)
      for(int j=h[i];j!=-1;j=b[j].ne)
        if(!b[j].w&&b[j].v!=0&&c[b[j].u]==c[b[j].v])
          jg--;
    printf("%d",jg);
    //while(1);
    return 0;
}