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 #include<iostream> 22 #include<cstring> 23 #include<cstdio> 24 #include<algorithm> 25 #include<vector> 26 #define M 55 27 #define N 1000 28 using namespace std; 29 vector<int>v[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 len=v[u].size(); 38 for(int i=0; i<len; ++i){ 39 int vu=v[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 cntR=1, cntC=1; 54 for(int i=1; i<=n; ++i) 55 scanf("%s", g[i]+1); 56 for(int i=1; i<=n; ++i) 57 for(int j=1; j<=m; ++j) 58 if(g[i][j]=='*'){ 59 aR[i][j]=cntR; 60 if(j+1>m || g[i][j+1]!='*') 61 ++cntR; 62 } 63 for(int j=1; j<=m; ++j) 64 for(int i=1; i<=n; ++i) 65 if(g[i][j]=='*'){ 66 aC[i][j]=cntC; 67 if(i+1>n || g[i+1][j]!='*') 68 ++cntC; 69 } 70 for(int i=1; i<=n; ++i) 71 for(int j=1; j<=m; ++j) 72 if(g[i][j]=='*') 73 v[aR[i][j]].push_back(aC[i][j]); 74 75 int ans=0; 76 memset(linker, 0, sizeof(linker)); 77 for(int i=1; i<cntR; ++i){ 78 memset(vis, 0, sizeof(vis)); 79 if(dfs(i)) ++ans; 80 } 81 printf("%d\n", ans); 82 for(int i=1; i<cntR; ++i) 83 v[i].clear(); 84 } 85 return 0; 86 }
?
)
)
)
