poj 2226 Muddy Fields(二分图最小点覆盖)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <string>
 5 #include <queue>
 6 #include <cstring>
 7 #include <vector>
 8 using namespace std;
 9 #define maxn 510 
10 int R, C;
11 int h[maxn][maxn], z[maxn][maxn];
12 char mp[55][55];
13 int line[maxn], vis[maxn];
14 int cnth, cntz, ans;
15 vector <int> q[maxn];
16 void init(){
17     memset(h, 0, sizeof(h));
18     memset(z, 0, sizeof(z));
19     memset(q, 0, sizeof(q));
20     cnth = 1;
21     for(int i = 1; i <= R; i++){
22         for(int j = 1; j <= C; j++){
23             if(mp[i][j] == ‘*‘) h[i][j] = cnth;
24             if(mp[i][j] == ‘*‘ && mp[i][j+1] != ‘*‘) cnth++;
25             
26         }
27     }
28     
29     cntz = 1;
30     for(int i = 1; i <= C; i++){
31         for(int j = 1; j <= R; j++){
32             if(mp[j][i] == ‘*‘) z[j][i] = cntz;
33             if(mp[j][i] == ‘*‘ && mp[j+1][i] != ‘*‘) cntz++;
34         }
35     }
36     
37     for(int i = 1; i <= R; i++){
38         for(int j = 1; j <= C; j++){
39             if(mp[i][j] == ‘*‘){
40                 q[h[i][j]].push_back(z[i][j]);
41             }
42         }
43     }
44 }
45 bool find(int x){
46     for(int i = 0; i < q[x].size(); i++){
47         if(!vis[ q[x][i] ] ){
48             vis[ q[x][i] ] = 1;
49             if(!line[q[x][i]] || find(line[q[x][i]])){
50                 line[q[x][i]] = x;
51                 return true;
52             }
53         }
54     }
55     return false;
56 }
57 void hungry(){
58     ans = 0;
59     memset(line, 0, sizeof(line));
60     for(int i = 1; i < 510; i++){
61         memset(vis, 0, sizeof(vis));
62         if(find(i)) ans++;
63     }
64     printf("%d\n", ans);
65     
66 }
67 int main(){
68     while(~scanf("%d%d", &R, &C)){
69         memset(mp, ‘-1‘, sizeof(mp));
70         for(int i = 1; i <= R; i++){
71             for(int j = 1; j <= C; j++) cin>>mp[i][j];
72         }
73         init();
74         hungry();
75     }
76 
77 
78     return 0;
79 }