poj 3020 Antenna Placement 二分圖匹配

黑白染色  然後求二分圖最大匹配[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std; 
const int maxn=40+9; 
int n,m; 
char a[maxn][maxn]; 
struct 
{ 
    int to,next; 
}e[maxn*10*4]; 
int head[maxn*10],lon; 
void edgeini() 
{ 
    memset(head,-1,sizeof(head)); 
    lon=-1; 
} 
void edgemake(int from,int to) 
{ 
    e[++lon].to=to; 
    e[lon].next=head[from]; 
    head[from]=lon; 
} 
 
int mat[maxn*10],vist[maxn*10]; 
bool work(int u) 
{ 
//    cout<<u<<endl;  
    vist[u]=1; 
    for(int k=head[u];k!=-1;k=e[k].next) 
    { 
        int v=e[k].to; 
        if(mat[v]==-1) 
        { 
            mat[v]=u; 
            return true; 
        } 
    } 
    for(int k=head[u];k!=-1;k=e[k].next) 
    { 
        int v=e[k].to; 
        if(vist[mat[v]]) continue; 
        if(work(mat[v])) 
        { 
            mat[v]=u; 
            return true; 
        } 
    } 
    return false; 
} 
 
int solve() 
{ 
    int ret=0; 
    for(int i=1;i<=n;i++) 
    for(int j=1;j<=m;j++) 
    { 
        if((i+j)%2==0) 
        { 
            memset(vist,0,sizeof(vist)); 
            ret+=work(i*m-m+j); 
        } 
//        cout<<i*m-m+j<<endl;  
    } 
    return(ret); 
} 
 
 
 
int main() 
{ 
//    freopen("in.txt","r",stdin);  
    int tcase; 
    scanf("%d",&tcase); 
    while(tcase--) 
    { 
        edgeini(); 
        memset(mat,-1,sizeof(mat)); 
        memset(a,0,sizeof(a)); 
        int ans=0; 
        scanf("%d %d",&n,&m); 
        for(int i=1;i<=n;i++) 
        scanf("%s",&a[i][1]); 
        for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) 
        if(a[i][j]=='*') 
        { 
            ans++; 
            if(a[i+1][j]=='*') 
            edgemake(i*m-m+j,i*m+j); 
            if(a[i-1][j]=='*') 
            edgemake(i*m-m+j,i*m-m-m+j); 
            if(a[i][j+1]=='*') 
            edgemake(i*m-m+j,i*m-m+j+1); 
            if(a[i][j-1]=='*') 
            edgemake(i*m-m+j,i*m-m+j-1); 
        } 
        int ret=solve(); 
        printf("%d\n",ans-ret); 
    } 
    return 0; 
}