注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

POJ 2226 Muddy Fields 二分匹配  

2011-02-09 18:17:11|  分类: 图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=2226

这个题的原型应该是Asteroids的变种,刚看了这道题,一眼就看出了是最小覆盖,看来我理解了最小覆盖的内在含义了。
农夫John的养牛场,是一个R 行C 列的矩形,一场大雨后,养牛场低洼的地方都有了积水。John 的牛都很娇贵的,他们吃草的时候,不想把他们的蹄子给弄脏了。为了不让牛儿们把它们的蹄子弄脏,John 决定把有水的地方铺上木板。他的木板是宽度为1,长度没有限制的。 

他想用最少数目的木板把所有有水的低洼处给覆盖上,前提是木板不能覆盖草地,但是可以重叠。
Sample:
4 4
*.*.
.***
***.
..*.

把行里面连在一起的坑连起来视为一个点,即一块横木板,编上序号,Sample则转化为:

1 0 2 0
0 3 3 3
4 4 4 0
0 0 5 0

把这些序号加入X集合,再按列做一次则为:

1 0 4 0
0 3 4 5
2 3 4 0
0 0 4 0

同样加入Y集合,一个坑只能被横着的或者被竖着的木板盖住,将原图的坑的也标上不同的序号,一共九个坑

1 . 2 .
. 3 4 5
67 8 .
. . 9 .

比如7号坑可以被横着的4号木板和竖着的3号木板盖住,把每个点的对应的横木板(4)和竖木板(3)中间连一条边的话,则问题转化为 找尽量少的边把这些点都盖住,根据定理便是求最大匹配数.

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
    int nx, ny;             // X的點數目、Y的點數目
 int mx[1000], my[1000];   // X各點的配對對象、Y各點的配對對象
 bool vy[1000];           // 紀錄Graph Traversal拜訪過的點
 bool adj[1000][1000];     // 精簡過的adjacency matrix
 
 // 以DFS建立一棵交錯樹
 bool DFS(int x)
 {
     for (int y=0; y<ny; ++y)
         if (adj[x][y] && !vy[y])
         {
             vy[y] = true;
 
             // 找到擴充路徑
                if (my[y] == -1 || DFS(my[y]))
             {
                mx[x] = y; my[y] = x;
                return true;
                }
         }
     return false;
 }
 
 int bipartite_matching()
 {
     // 全部的點初始化為未匹配點。
     memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
 
     // 依序把X中的每一個點作為擴充路徑的端點,
     // 並嘗試尋找擴充路徑。
     int c = 0;
     for (int x=0; x<nx; ++x)
//     if (mx[x] == -1)    // x為未匹配點,這行可精簡。
         {
             // 開始Graph Traversal
             memset(vy, false, sizeof(vy));
             if (DFS(x)) c++;
         }
     return c;
 }
 main()
 {
          int a,i,j,r,c,p[51][51];
          char g[51][51];
          while(scanf("%d%d",&r,&c)!=EOF)
          {
             memset(adj, 0, sizeof(adj));
             getchar();
             for(i=0;i<r;i++)
               gets(g[i]);
             a=0;
             for(i=0;i<r;i++)
             for(j=0;j<c;j++)
             {
                if(g[i][j]!='*')
                  continue;               
                else if(j==0||g[i][j-1]!='*')
                  p[i][j]=a++;
                else
                  p[i][j]=a-1;
             }
             nx=a;
             a=0;
             for(j=0;j<c;j++)
             for(i=0;i<r;i++)
             {
                if(g[i][j]!='*')
                 continue;
                else if(i==0||g[i-1][j]!='*')
                {
                 adj[p[i][j]][a]=1;
                 a++;
                }
                else
                  adj[p[i][j]][a-1]=1;
             }
             ny=a;
             printf("%d\n",bipartite_matching());
          }
          system("pause");
 }

  评论这张
 
阅读(151)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018