ZOJ 1654 匈牙利算法二分图匹配 Place the Robots

给每行上的空地编不同号，就算在同一行上，但是被墙壁隔开了的话也编不同的号，一个编号对应一个顶点，这样的顶点放在集合XI中。

给每列上的空地编不同号，就算在同一行上，但是被墙壁隔开了的话也编不同的号，一个编号对应一个顶点，这样的顶点放在集合YI中。

如果XI中的某个顶点i和YI中的某个顶点j是在同一个空地上，那么i和j有一条边相连。

通过如上方法构造出一个二部图（也叫二分图），然后用匈牙利算法做最大二部图匹配，就OK了，我是通过DFS寻找增广路。

贴代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #define MAXN 55
  4 #define MA 2550
  5 char a[MAXN][MAXN];//输入的地图
  6 int xs[MAXN][MAXN],ys[MAXN][MAXN];//行与列的编号情况
  7 int m,n; //m行,n列
  8 bool g[MA][MA];//记录行编号与列编号的交叉情况
  9 bool s[MA];//DFS时记录是否被访问过
 10 int xx[MA],yy[MA];//记录每个行编号匹配的列编号及列编号匹配的行编号
 11 int X,Y;//行列的最后一个编号，从0开始编
 12 void init()
 13 {
 14     int i,j;
 15     bool flag;
 16     scanf("%d%d",&m,&n);
 17     memset(xs,0xff,sizeof(xs));
 18     memset(ys,0xff,sizeof(ys));
 19     for(i=0; i<m; ++i)  //读入数据
 20         scanf("%s",a[i]);
 21     X=-1;
 22     for(i=0; i<m; ++i)  //给每行没有被墙壁隔开的空地编同一个号，被墙壁隔开编不同号，不同行编不同号
 23     {
 24         flag = false;
 25         for(j=0; j<n; ++j)
 26         {
 27             if(a[i][j] == 'o' )
 28             {
 29                 if(!flag)   X++;
 30                 xs[i][j] = X;
 31                 flag = true;
 32             }
 33             else if(a[i][j] == '#')
 34                 flag = false;
 35         }
 36     }
 37     Y = -1;
 38     for(j=0; j<n; ++j) //给每列编号，同上类似
 39     {
 40         flag = false;
 41         for(i=0; i<m; ++i)
 42         {
 43             if(a[i][j] == 'o')
 44             {
 45                 if(!flag) Y++;
 46                 flag = true;
 47                 ys[i][j] = Y;
 48             }
 49             else if(a[i][j] =='#')
 50                 flag = false;
 51         }
 52     }
 53     memset(g,0,sizeof(g));
 54     for(i=0; i<m; ++i) //如果该空地既有行编号又有列编号，那么编号xs[i][j]与ys[i][j]有边相连
 55         for(j=0; j<n; ++j)
 56             if(xs[i][j] != -1 && ys[i][j] != -1)
 57                 g[xs[i][j]][ys[i][j]] = 1;
 58 }
 59 bool path(int u)
 60 {
 61     int v;
 62     for(v=0; v<=Y; ++v)//考虑所有YI顶点
 63     {
 64         if(g[u][v] && !s[v])//v和u邻接且未访问过
 65         {
 66             s[v] = 1;
 67             if(yy[v] == -1 || path(yy[v]))//V没被匹配过或者V已经被匹配，但能从yy[v]出发找到一条增广路
 68             {
 69                 xx[u] = v;//V匹配给U，U匹配给V
 70                 yy[v] = u;
 71                 return 1;
 72             }
 73         }
 74     }
 75     return 0;
 76 }
 77 void maxMatch()
 78 {
 79     int i,ans =0;
 80     memset(xx,0xff,sizeof(xx));
 81     memset(yy,0xff,sizeof(yy));
 82     for(i=0; i<=X; ++i)//从所有XI中的未盖点出发寻找增广路
 83     {
 84         if(xx[i]==-1)
 85         {
 86             memset(s,0,sizeof(s));
 87             if(path(i))
 88                 ++ans;
 89         }
 90     }
 91     printf("%d\n",ans);
 92 }
 93 int main()
 94 {
 95 //    freopen("in.cpp","r",stdin);
 96     int T;
 97     scanf("%d",&T);
 98     for(int d =1; d<=T; ++d)
 99     {
100         printf("Case :%d\n",d);
101         init();
102         maxMatch();
103     }
104     return 0;
105 }

ZOJ 1654 匈牙利算法 二分图匹配 Place the Robots

ZOJ 1654 匈牙利算法二分图匹配 Place the Robots