以前写过的题，翻出来学习网络流写二分图匹配，因为复杂度更优秀，$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 ;
}