ZOJ 1516 Uncle Tom's Inherited Land

题目大意：

除去那些作为荷塘的土地块，将剩余的土地希望每次将两块相邻的地一起卖出，最多能卖出多少种这样的由相邻土地

合成的长方形土地块

很明显的二分图问题，但是要考虑如何建模

一个长方形土地总是由相邻的两块地组成，那么我们就将相邻的两块地一块放在X集合，一块放在Y集合

所有放在X集合中的土地互不影响（也就是任意两个在X中的土地不形成长方形）

那么我们可以看作土地上

0101010

1010101

0101010

1010101

比如这样标注的，那么0所对应的空地就放入集合X，并不断添加一个X的标号

同理，1所在空地添入集合Y，并不断添加一个Y的标号

剩下的就是用匈牙利算法求X到Y的最大匹配了

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn = ;

 int n , m , k;

 int g[maxn][maxn] , cx[maxn] , cy[maxn] , visy[maxn] , nx , ny;

 bool col[][];//判断是否为鱼塘

 struct Point{

     int x , y;

     Point(int x= , int y=):x(x),y(y){}

 };

 Point px[maxn] , py[maxn];

 bool ok(Point p1 , Point p2)

 {

     if((p1.x == p2.x && abs(p1.y - p2.y) == ) || (p1.y == p2.y && abs(p1.x - p2.x) == ))

         return true;

     return false;

 }

 void build_graph()

 {

     memset(g ,  , sizeof(g));

     for(int i= ; i<=nx ; i++){

         for(int j= ; j<=ny ; j++){

             if(ok(px[i] , py[j]))

                 g[i][j] = ;

         }

     }

 }

 int dfs(int u)

 {

     for(int v =  ; v<=ny ; v++)

         if(g[u][v] && !visy[v]){

             visy[v] = ;

             if(cy[v] == - || dfs(cy[v])){

                 cx[u] = v;

                 cy[v] = u;

                 return ;

             }

         }

     return ;

 }

 int MaxMatch()

 {

     memset(cx , - , sizeof(cx));

     memset(cy , - , sizeof(cy));

     int ans = ;

     for(int i= ; i<=nx ; i++){

         if(cx[i] == -){

             memset(visy ,  , sizeof(visy));

             ans += dfs(i);

         }

     }

     return ans;

 }

 int main()

 {

   //  freopen("a.in" , "r"  ,stdin);

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

     {

         scanf("%d" , &k);

         int x , y;

         memset(col ,  , sizeof(col));

         while(k--){

             scanf("%d%d" , &x , &y);

             col[x][y] = ;

         }

         nx =  , ny = ;

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

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

                 if(!col[i][j]){

                     if((i+j)&) py[++ny] = Point(i,j);

                     else px[++nx] = Point(i,j);

                 }

         //构造二分图

         build_graph();

         printf("%d\n" , MaxMatch());

     }

     return ;

 }

巴特西

ZOJ 1516 Uncle Tom's Inherited Land

最新文章

热门文章