1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 100009 5 #define inf 2139062143 6 using namespace std; 7 int n,m,a[102][102],cnt=1,T,ans,head[M],d[M],q[2*M],next[10*M],u[10*M],v[10*M]; 8 int xx[4]={
   0,0,1,-1},yy[4]={
   1,-1,0,0}; 9 bool bfs()10 {11     memset(d,0,sizeof(int)*(T+1));12     int h=0,t=1;13     q[1]=0;14     d[0]=1;15     for(;h
        
         n||ny>m)81                      continue;82                    if(a[nx][ny]!=a[i][j]||a[i][j]==0)83                      jia((i-1)*m+j,(nx-1)*m+ny,1);84                 }85         }86     for(;bfs();)87       ans+=dinic(0,0x7fffffff);88     printf("%d\n",ans);89     return 0;90 }
        
       
      
     

最小割，不同的点之间进行连边，空地于空地之间连边，易知最小割极为答案。