---恢复内容开始---

题意

　　N*N的土地，某些点被挖成池塘了，其余为空地， 现在要组织成1*2的空地出售，问最大能出售的数量。

解题思路

　　因为 R*C - K  <= 50  意味着，去除掉池塘后最多只有50个空地

　　每个顶点与其上下左右的空地 连接，然后 构成二分图。  转换成求最大独立边（任意两条边不共用相同顶点）即为最大匹配。

#include
     
      #include
      
       #include
       
        const int N = 110;int r, c, n, m, k;bool g[N][N], use[N][N];int ma[N], mb[N], num[N][N];bool vis[N];int dir[4][2] = { {
   0,1},{
   1,0},{
   0,-1},{-1,0} };int path( int u ){     for(int v = 0; v < n; v++){         if( g[u][v] && !vis[v] ){             vis[v] = 1;            if( ma[v] == -1 || path( ma[v] )){                ma[v] = u; mb[u] = v;                return 1;                }            }        }        return 0;}int main(){    while( scanf("%d%d",&r,&c ) , r+c ){        memset( use, 0, sizeof(use));        memset( g, 0, sizeof(g));        scanf("%d", &k);        int a, b;        for(int i = 0; i < k; i++){            scanf("%d%d", &a,&b);            use[a][b] = 1;        }        n = 0;        for(int i = 1; i <= r; i++)            for(int j = 1; j <= c; j++){                if( !use[i][j] ){                     num[i][j] = n++;                }                }        for(int i = 1; i <= r; i++)            for(int j = 1; j <= c; j++){                if( !use[i][j] ){                    for(int d = 0; d < 4; d++){                        int x = i+dir[d][0], y = j+dir[d][1];                        if(  (x>=1)&&(x<=r)&&(y>=1)&&(y<=c) && !use[x][y] ){                            g[ num[i][j] ][ num[x][y] ]= 1;                            g[ num[x][y] ][ num[i][j] ] = 1;                            }                        }                    }                }         memset( ma, 0xff, sizeof(ma));        memset( mb, 0xff, sizeof(mb));        int res = 0;        for(int i = 0; i < n; i++){            if( mb[i] == -1 ){                 memset( vis, 0, sizeof(vis));                res += path( i );            }            }        printf("%d\n", res/2 );    }    return 0;    }
       
      
     

 

---恢复内容结束---