做一个介绍网站多少钱,百度关键词指数工具,微小店网站建设多少钱,建设商业门户网站的重要性题意#xff1a;给出一个图#xff0c;其中有 . 和 X 两种#xff0c;. 为通路#xff0c;X表示墙#xff0c;在其中放炸弹#xff0c;然后炸弹不能穿过墙#xff0c;问你最多在图中可以放多少个炸弹#xff1f; 这个题建图有点复杂orz。 建图#xff0c;首先把每一行…题意给出一个图其中有 . 和 X 两种. 为通路X表示墙在其中放炸弹然后炸弹不能穿过墙问你最多在图中可以放多少个炸弹 这个题建图有点复杂orz。 建图首先把每一行中的可以放一个炸弹的一块区域标记为同一个数字数字不重复然后列做相同的处理即缩点 缩点之后原图矩阵中每个点都对用一个行数字和一个列数字然后按照这两个数字进行二分匹配其相同值只取一个得到的结果就是ans。 1 #includeiostream2 #includecstring3 #includeiostream4 #includealgorithm5 #define maxn 106 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 i0;icnt_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 i0;in;i){
26 for (int j0;jn;j){
27 cin map[i][j];
28 }
29 }
30 memset(row,-1,sizeof(row));
31 memset(col,-1,sizeof(col));
32 cnt_row0,cnt_col0;
33 for (int i0;in;i){
34 for (int j0;jn;j){
35 if (map[i][j]. row[i][j]-1){
36 for (int kj;map[i][k]. kn;k) row[i][k]cnt_row;
37 cnt_row;
38 }
39 if (map[j][i]. col[j][i]-1){
40 for (int kj;map[k][i]. kn;k) col[k][i]cnt_col;
41 cnt_col;
42 }
43 }
44 }
45 memset(line,0,sizeof(line));
46 for (int i0;in;i){
47 for (int j0;jn;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 ans0;
53 memset(match,-1,sizeof(match));
54 for (int i0;icnt_row;i){
55 memset(used,0,sizeof(used));
56 if (dfs(i)) ans;
57 }
58 cout ans endl;
59 }
60 return 0;
61 } 转载于:https://www.cnblogs.com/changer-qyz/p/8650321.html
