首页 > 代码库 > ZOJ 1516 Uncle Tom's Inherited Land
ZOJ 1516 Uncle Tom's Inherited Land
题目大意：
除去那些作为荷塘的土地块，将剩余的土地希望每次将两块相邻的地一起卖出，最多能卖出多少种这样的由相邻土地
合成的长方形土地块
很明显的二分图问题，但是要考虑如何建模
一个长方形土地总是由相邻的两块地组成，那么我们就将相邻的两块地一块放在X集合，一块放在Y集合
所有放在X集合中的土地互不影响（也就是任意两个在X中的土地不形成长方形）
那么我们可以看作土地上
0101010
1010101
0101010
1010101
比如这样标注的，那么0所对应的空地就放入集合X，并不断添加一个X的标号
同理，1所在空地添入集合Y，并不断添加一个Y的标号
剩下的就是用匈牙利算法求X到Y的最大匹配了
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 using namespace std; 5 6 const int maxn = 55; 7 int n , m , k; 8 int g[maxn][maxn] , cx[maxn] , cy[maxn] , visy[maxn] , nx , ny; 9 bool col[105][105];//判断是否为鱼塘10 11 struct Point{12 int x , y;13 Point(int x=0 , int y=0):x(x),y(y){}14 };15 16 Point px[maxn] , py[maxn];17 18 bool ok(Point p1 , Point p2)19 {20 if((p1.x == p2.x && abs(p1.y - p2.y) == 1) || (p1.y == p2.y && abs(p1.x - p2.x) == 1))21 return true;22 return false;23 }24 25 void build_graph()26 {27 memset(g , 0 , sizeof(g));28 for(int i=1 ; i<=nx ; i++){29 for(int j=1 ; j<=ny ; j++){30 if(ok(px[i] , py[j]))31 g[i][j] = 1;32 }33 }34 }35 36 int dfs(int u)37 {38 for(int v = 1 ; v<=ny ; v++)39 if(g[u][v] && !visy[v]){40 visy[v] = 1;41 if(cy[v] == -1 || dfs(cy[v])){42 cx[u] = v;43 cy[v] = u;44 return 1;45 }46 }47 return 0;48 }49 50 int MaxMatch()51 {52 memset(cx , -1 , sizeof(cx));53 memset(cy , -1 , sizeof(cy));54 int ans = 0;55 for(int i=1 ; i<=nx ; i++){56 if(cx[i] == -1){57 memset(visy , 0 , sizeof(visy));58 ans += dfs(i);59 }60 }61 return ans;62 }63 64 int main()65 {66 // freopen("a.in" , "r" ,stdin);67 while(scanf("%d%d" , &n , &m) , n)68 {69 scanf("%d" , &k);70 int x , y;71 memset(col , 0 , sizeof(col));72 while(k--){73 scanf("%d%d" , &x , &y);74 col[x][y] = 1;75 }76 nx = 0 , ny = 0;77 for(int i=1 ; i<=n ; i++)78 for(int j=1 ; j<=m ; j++)79 if(!col[i][j]){80 if((i+j)&1) py[++ny] = Point(i,j);81 else px[++nx] = Point(i,j);82 }83 //构造二分图84 build_graph();85 printf("%d\n" , MaxMatch());86 }87 return 0;88 }
ZOJ 1516 Uncle Tom's Inherited Land
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。