爱心建站网,重庆网站建设案例,goood 谷德设计网官网,太原seo公司1 /*2 题意#xff1a;用木板盖住泥泞的地方#xff0c;不能盖住草。木板任意长#xff01;可以重叠覆盖#xff01; *表示泥泞的地方#xff0c;.表示草#xff01;3 思路#xff1a;4 首先让我们回忆一下HDU 2119 Matrix这一道题#xff0c;一个矩阵… 1 /*2 题意用木板盖住泥泞的地方不能盖住草。木板任意长可以重叠覆盖 *表示泥泞的地方.表示草3 思路4 首先让我们回忆一下HDU 2119 Matrix这一道题一个矩阵中只有0 1然后让我们通过选择一行或者5 是一列将其所在行的或者所在列的 1全部删掉求出最少需要几步6 7 这道题的思路就是将行标 和 列标值为1的建立一条边通过匈牙利算法可以得到这个二分图的最大匹配数8 最大匹配数最小顶点覆盖数最小顶点覆盖就是用最少的点覆盖了这个二分图的所有的边然后去掉这些9 最小覆盖中的顶点就可以去掉所有的边也就是所有的 1都去掉了
10
11 那么这道题该怎么办呢其实和上面的思路差不多只不过是不能在原图上解题这道题每一行或者每一列
12 都有限制的因素就是草地覆盖泥泞的地方时不能覆盖草地所以要想办法忽略草地的影响
13
14 解决方法连通块的思路 如果一个连通区域的左右两侧无法延伸则为行连通块儿上下无法延伸则为列连通块儿把行连通块儿作为X集合列连通块儿作为Y集合则X与Y相连得到的边就代表所要覆盖的 泥泞区域。即可用匈牙利算法求出覆盖所有泥泞区域所需要的最少连通块儿。 1现将每一行的不连在一起的泥泞土地赋给不同的编号从1...cntR开始也就是如果忽略
15 草地的话泥泞的地方一共有cntR个行连通块
16 2同理每一列按照每一行的操作 共有cntC个列连通块
17 这样结题思路就和上面的那一道题一样了.....
18
19 g[i][j]* 那么aR[i][j]就是该点新的行标 aC[i][j]就是该点行的列标
20 */
21 #includeiostream
22 #includecstring
23 #includecstdio
24 #includealgorithm
25 #includevector
26 #define M 55
27 #define N 1000
28 using namespace std;
29 vectorintv[N];
30 char g[M][M];
31 int vis[N];
32 int linker[N];
33 int aR[M][M], aC[M][M];
34 int n, m;
35
36 bool dfs(int u){
37 int lenv[u].size();
38 for(int i0; ilen; i){
39 int vuv[u][i];
40 if(!vis[vu]) {
41 vis[vu]1;
42 if(!linker[vu] || dfs(linker[vu])){
43 linker[vu]u;
44 return true;
45 }
46 }
47 }
48 return false;
49 }
50
51 int main(){
52 while(scanf(%d%d, n, m)!EOF){
53 int cntR1, cntC1;
54 for(int i1; in; i)
55 scanf(%s, g[i]1);
56 for(int i1; in; i)
57 for(int j1; jm; j)
58 if(g[i][j]*){
59 aR[i][j]cntR;
60 if(j1m || g[i][j1]!*)
61 cntR;
62 }
63 for(int j1; jm; j)
64 for(int i1; in; i)
65 if(g[i][j]*){
66 aC[i][j]cntC;
67 if(i1n || g[i1][j]!*)
68 cntC;
69 }
70 for(int i1; in; i)
71 for(int j1; jm; j)
72 if(g[i][j]*)
73 v[aR[i][j]].push_back(aC[i][j]);
74
75 int ans0;
76 memset(linker, 0, sizeof(linker));
77 for(int i1; icntR; i){
78 memset(vis, 0, sizeof(vis));
79 if(dfs(i)) ans;
80 }
81 printf(%d\n, ans);
82 for(int i1; icntR; i)
83 v[i].clear();
84 }
85 return 0;
86 } 转载于:https://www.cnblogs.com/hujunzheng/p/3918485.html
