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 }
再思考一下匈牙利算法：这里用的是深度优先的方法，对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 }