hdu 5093 Battle ships 二分图匹配-白红宇

hdu 5093 Battle ships 二分图匹配

阅读量：5260 次

发布时间：2019-06-14

本文共 2140 字，大约阅读时间需要 7 分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5093

一开始就往贪心的方向想了结果wa全场

这种矩阵形式的图一般要联想到行和列构成了二分图

然后实质就是求一个最大匹配

中间的冰山实际上就是把一行或一列切成多个顶点而已

所以一开始预处理一下然后就可以套用模板

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               using namespace std;const int maxn = 60;const int maxv = 4000;char a[maxn][maxn];int V;vector
                
                  G[maxv];int match[maxv];bool used[maxv];void addedge(int u, int v){ G[u].push_back(v); G[v].push_back(u);}bool dfs(int v){ used[v] = true; for(int i = 0; i < G[v].size(); i++) { int u = G[v][i], w = match[u]; if(w < 0 || !used[w] && dfs (w)) { match[v] = u; match[u] = v; return true; } } return false;}int bipartite_matching(){ int res = 0; memset(match, -1, sizeof(match)); for(int v = 0; v < V; v++) { if(match[v] < 0) { memset(used, 0, sizeof(used)); if(dfs(v)) res++; } } return res;}int r[maxn][maxn];int c[maxn][maxn];int rcnt[maxn];int ccnt[maxn];int main(){ //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); while(T--) { memset(rcnt, 0, sizeof(rcnt)); memset(ccnt, 0, sizeof(ccnt)); int m, n; scanf("%d%d", &m, &n); V = (m + n) * 30; for(int i = 0; i < V; i++) G[i].clear(); for(int i = 0; i < m; i++) scanf("%s", a[i]); for(int i = 0; i < m; i++) { bool flag = false; for(int j = 0; j < n; j++) { if(a[i][j] == '*') flag = true; if(flag && a[i][j] == '#') { r[i][rcnt[i]++] = j; //记录每一段的终点/最大值（开区间） flag = false; } } r[i][rcnt[i]++] = n; //不太严谨，不过此题不影响结果 } for(int j = 0; j < n; j++) { bool flag = false; for(int i = 0; i < m; i++) { if(a[i][j] == '*') flag = true; if(flag == true && a[i][j] == '#') { c[j][ccnt[j]++] = i; flag = false; } } c[j][ccnt[j]++] = m; } for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) { if(a[i][j] == '*') { int rloc; for(int k = 0; k < rcnt[i]; k++) { if(j < r[i][k]) { rloc = k; break; } } int cloc; for(int k = 0; k < ccnt[j]; k++) { if(i < c[j][k]) { cloc = k; break; } } addedge(i*30 + rloc, m*30 + j*30 + cloc); } } printf("%d\n", bipartite_matching()); } return 0;}