hdoj1045 Fire Net（二分图最大匹配）

题意：给出一个图，其中有 . 和 X 两种，. 为通路，X表示墙，在其中放炸弹，然后炸弹不能穿过墙，问你最多在图中可以放多少个炸弹？

这个题建图有点复杂orz。

建图，首先把每一行中的可以放一个炸弹的一块区域标记为同一个数字，数字不重复，然后列做相同的处理，即缩点！

缩点之后原图矩阵中每个点都对用一个行数字和一个列数字，然后按照这两个数字进行二分匹配，其相同值只取一个，得到的结果就是ans。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define maxn 10
 6 using namespace std;
 7 int n;
 8 int cnt_row,cnt_col;
 9 char map[maxn][maxn];
10 int line[maxn][maxn],row[maxn][maxn],col[maxn][maxn],match[maxn],used[maxn];
11 int dfs(int x){
12     for (int i=0;i<cnt_col;i++){
13         if (line[x][i]==1 && !used[i]){
14             used[i]=1;
15             if (match[i]==-1 || dfs(match[i])){
16                 match[i]=x;
17                 return 1;
18             }
19         }
20     }
21     return 0;
22 }
23 int main(){
24     while (cin >> n && n){
25         for (int i=0;i<n;i++){
26             for (int j=0;j<n;j++){
27                 cin >> map[i][j];
28             }
29         }
30         memset(row,-1,sizeof(row));
31         memset(col,-1,sizeof(col));
32         cnt_row=0,cnt_col=0;
33         for (int i=0;i<n;i++){
34             for (int j=0;j<n;j++){
35                 if (map[i][j]=='.' && row[i][j]==-1){
36                     for (int k=j;map[i][k]=='.' && k<n;k++) row[i][k]=cnt_row;
37                     cnt_row++;
38                 }
39                 if (map[j][i]=='.' && col[j][i]==-1){
40                     for (int k=j;map[k][i]=='.' && k<n;k++) col[k][i]=cnt_col;
41                     cnt_col++;
42                 }
43             }
44         }
45         memset(line,0,sizeof(line));
46         for (int i=0;i<n;i++){
47             for (int j=0;j<n;j++){
48                 if (map[i][j]=='.' && row[i][j]!=-1 && col[i][j]!=-1) 
49                     line[row[i][j]][col[i][j]]=1;
50             }
51         }
52         int ans=0;
53         memset(match,-1,sizeof(match));
54         for (int i=0;i<cnt_row;i++){
55                 memset(used,0,sizeof(used));
56                 if (dfs(i)) ans++;
57         }
58         cout << ans << endl;
59     }
60     return 0;
61 }

hdoj1045 Fire Net（二分图最大匹配）

相关推荐