解题：BZOJ 4808 马

题面

以前写过的题，翻出来学习网络流写二分图匹配，因为复杂度更优秀，$Dinic$是$O(sqrt(n)m)$哒~

原点向左部点连流量为$1$的边，左部点向对应右部点连流量为$1$的边，右部点向汇点连流量为$1$的边，然后跑

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int B=,N=,M=,inf=1e9;

 const int mov[][]={{,},{,-},{-,},{-,-},{,},{,-},{-,},{-,-}};

 int T,n,m,s,t,f,b,t1,t2,rd,num,cnt,tot,ans;

 int noww[*M],goal[*M],flow[*M];

 int p[N],pp[N],dep[N],que[N];

 int bro[B][B],mapp[B][B];

 int tonum(int x,int y)

 {

     return (x-)*m+y;

 }

 bool check(int x,int y)

 {

     return x>=&&x<=n&&y>=&&y<=m;

 }

 void link(int f,int t,int v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,flow[cnt]=v;

     noww[++cnt]=p[t],p[t]=cnt;

     goal[cnt]=f,flow[cnt]=;

 }

 bool Layering(int st,int ed)

 {

     for(int i=;i<=num;i++) pp[i]=p[i];

     memset(dep,-,sizeof dep);

     dep[st]=,que[f=b=]=st;

     while(f<=b)

     {

         int tn=que[f++];

         for(int i=p[tn];i;i=noww[i])

             if(dep[goal[i]]==-&&flow[i])

                 dep[goal[i]]=dep[tn]+,que[++b]=goal[i];

     }

     return ~dep[ed];

 }

 int Augmenting(int nd,int ed,int mn)

 {

     if(nd==ed||!mn) return mn;

     int tmp=,tep=;

     for(int i=pp[nd];i;i=noww[i])

     {

         pp[nd]=i;

         if(dep[goal[i]]==dep[nd]+)

             if(tep=Augmenting(goal[i],ed,min(mn,flow[i])))

             {

                 flow[i]-=tep,mn-=tep;

                 flow[i^]+=tep,tmp+=tep;

                 if(!mn) break;

             }

     }

     return tmp;

 }

 void Dinic_Maxflow(int st,int ed)

 {

     while(Layering(st,ed))

         ans+=Augmenting(st,ed,inf);

 }

 int main ()

 {

     scanf("%d%d",&n,&m);

     cnt=,num=n*m+,tot=n*m,s=n*m+,t=n*m+;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

         {

             scanf("%d",&rd);

             bro[i][j]=rd,tot-=rd;

         }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(!bro[i][j])

             {

                 if((i^j)&)

                 {

                     link(s,tonum(i,j),);

                     for(int k=;k<;k++)

                     {

                         t1=i+mov[k][],t2=j+mov[k][];

                         if(check(t1,t2)&&!bro[t1][t2])

                             link(tonum(i,j),tonum(t1,t2),);

                     }

                 }

                 else link(tonum(i,j),t,);

             }

     Dinic_Maxflow(s,t);

     printf("%d",tot-ans);

     return ;

 }