1.09 ZOJ 1654 Place the Robots

浏览数：29 / 时间：2015年06月12日

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654

数算实习课的题，拿来算是热身了。顺便复习一下匈牙利算法。

若用独立集来解，是NPC问题；可以建模为二部图，将每一行每一列被墙隔开，且包含空地的连续区域看作一“块”。显然，一个块中最多放一个机器人，将横向块和纵向块分别编号，最大公共空地（最大匹配）即为最多机器人放置方法。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 const int MAXN = 5001;
 5 int n1, n2, m2[MAXN];
 6 bool b[MAXN][MAXN], vis[MAXN];
 7 
 8 int dfs(int x)
 9 {
10     for(int i=1 ; i<=n2 ; i++)
11         if(b[x][i] && vis[i] == 0)
12         {
13             vis[i] = 1;
14             if(m2[i] == 0 || dfs(m2[i]))
15             {
16                 m2[i] = x;
17                 return 1;
18             }
19         }
20     return 0;
21 }
22 
23 int main()
24 {
25     // freopen("input", "r", stdin);
26     int t, r, c;    scanf("%d", &t);
27     char m[60][60] = {0};
28     for(int Case=1 ; Case<=t ; Case++)
29     {
30         scanf("%d %d", &r, &c);
31         for(int i=1 ; i<=r ; i++)
32             scanf("%s", m[i]+1);
33         memset(b, 0, sizeof(b));
34         memset(m2, 0, sizeof(m2));
35         n1 = n2 = 0;
36         int d1[60][60] = {0}, d2[60][60] = {0};
37         for(int i=1 ; i<=r ; i++)
38             for(int j=1 ; j<=c ; j++)
39                 if(m[i][j] == ‘o‘)
40                     d1[i][j] = d1[i][j-1] ? d1[i][j-1] : ++n1;
41                 else
42                     d1[i][j] = m[i][j] == ‘#‘ ? 0 : d1[i][j-1];
43         for(int j=1 ; j<=c ; j++)
44             for(int i=1 ; i<=r ; i++)
45                 if(m[i][j] == ‘o‘)
46                     d2[i][j] = d2[i-1][j] ? d2[i-1][j] : ++n2;
47                 else
48                     d2[i][j] = m[i][j] == ‘#‘ ? 0 : d2[i-1][j];
49         for(int i=1 ; i<=r ; i++)
50             for(int j=1 ; j<=c ; j++)
51                 if(m[i][j] == ‘o‘)
52                     b[d1[i][j]][d2[i][j]] = 1;
53         int sum = 0;
54         for(int i=1 ; i<=n1 ; i++)
55         {
56             memset(vis, 0, sizeof(vis));
57             sum += dfs(i);
58         }
59         printf("Case :%d\n%d\n", Case, sum);
60     }
61 }

View Code

再思考一下匈牙利算法：这里用的是深度优先的方法，对m1中的每一个元素来dfs，返回值表示若找到了匹配，则sum+1。在dfs函数中，深度优先体现在，只要找到一个跟当前x匹配的元素i，不管i是否是已匹配饱和点，都让x试着与i匹配，然后递归看与i的原配m2[i]能否在找到“新欢”。若能找到，表示找到了一条增广路径并顺便增广了；否则就成了上一个抢下一个的“原配”，使最后一个成了光棍，但总匹配数不变，sum也就不加一。vis对每个x都要更新，标记了在匹配x的过程中改变过的m2中的元素，其深搜剪枝在于若m2中元素p被vis更新，则其原配必已考虑过，以后则不用考虑（代码体现在if(b[x][i] && vis[i] == 0) then...）。

匈牙利算法代码可以考虑背下来，当然背的前提是要理解。

这里在说一道二分图最大匹配的题，也是数算实习中的作业http://poj.org/problem?id=1325，今天仔细想了下细节。

这道题的关键是证明最小点覆盖解题的合理性。对于每一个job，可以在A机器i模式下做，也可以在B机器j模式下做，故贪心的说，对模式i，我们可以把其能做的job都做完再切换，即求出最少的点（最少的切换次数）使每一条边都被覆盖即可。还有一个细节是AB机器初始均在状态0，所以我们只需考虑在除0外的点即可。

想通是二分图求最小点覆盖后，根据柯尼希定理，只需求最大匹配即可。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int MAXN = 101;
 4 int m2[MAXN], n1, n2, line;
 5 bool b[MAXN][MAXN], vis[MAXN];
 6 
 7 int dfs(int x)
 8 {
 9     for(int i=1 ; i<n2 ; i++)
10         if(b[x][i] && vis[i] == 0)
11         {
12             vis[i] = 1;
13             if(m2[i] == 0 || dfs(m2[i]))
14             {
15                 m2[i] = x;
16                 return 1;
17             }
18         }
19     return 0;
20 }
21 
22 int main()
23 {
24     // freopen("input", "r", stdin);
25     while(scanf("%d %d %d", &n1, &n2, &line) == 3)
26     {
27         memset(b, 0, sizeof(b));
28         while(line--)
29         {
30             int i, j, tmp;
31             scanf("%d %d %d", &tmp, &i, &j);
32             b[i][j] = 1;
33         }
34         memset(m2, 0, sizeof(m2));
35         int sum = 0;
36         for(int i=1 ; i<n1 ; i++)
37         {
38             memset(vis, 0, sizeof(vis));
39             sum += dfs(i);
40         }
41         printf("%d\n", sum);
42     }
43 }