首页 > 代码库 > codeforces723 D. Lakes in Berland(并查集)

codeforces723 D. Lakes in Berland(并查集)

题目链接:codeforces723 D. Lakes in Berland

房教教我的,我按他思路写了好久才过,我好菜啊

房教的博客:http://www.cnblogs.com/Geek-xiyang/p/5930245.html

技术分享
  1 #include<cstdio>  2 #include<cstring>  3 #include<vector>  4 #include<algorithm>  5 #define CLR(a,b) memset((a),(b),sizeof((a)))  6 using namespace std;  7 const int N = 52;  8 const int M = 2800;  9 int n, m, k; 10 char ch[N][N]; 11 int val[N][N]; 12 int fa[M], num[M]; 13 bool vis[M]; 14 int dx[] = {0,0,1,-1}; 15 int dy[] = {1,-1,0,0}; 16 void init(){ 17     CLR(ch,.); 18     int cnt = 0; 19     for(int i = 0; i <= n+1; ++i) 20         for(int j = 0; j <= m+1; ++j) 21             val[i][j] = ++cnt; 22     for(int i = 1; i <= cnt; ++i){ 23         fa[i] = i; 24         num[i] = 1; 25     } 26 } 27 int fin(int x){ 28     if(x != fa[x]) 29         fa[x] = fin(fa[x]); 30     return fa[x]; 31 } 32 void uni(int x, int y){ 33     if((x = fin(x)) == (y = fin(y))) return; 34     else { 35         fa[x] = y; 36         num[y] += num[x]; 37     } 38 } 39 void make(int i, int j){ 40     for(int k = 0; k < 4; ++k){ 41         if(ch[dx[k]+i][dy[k]+j] == .) 42             uni(val[i][j], val[dx[k]+i][dy[k]+j]); 43     } 44 } 45 bool cmp(int x, int y){ 46     return num[x] < num[y]; 47 } 48 vector<int>v; 49 int main(){ 50     int i, j, kk, rt, t; 51     scanf("%d%d%d", &n, &m, &k); 52     init(); 53     for(i = 0; i <= n+1; ++i){ 54         uni(val[0][0], val[i][0]); 55         uni(val[0][0], val[i][m+1]); 56     } 57     for(i = 0; i <= m+1; ++i){ 58         uni(val[0][0], val[0][i]); 59         uni(val[0][0], val[n+1][i]); 60     } 61     for(i = 1; i <= n; ++i){ 62         scanf("%s", ch[i]+1); 63         ch[i][m+1] = .;//第二遍改时把这句漏了继续WA 64     } 65     for(i = 1; i <= n; ++i) 66         for(j = 1 ; j <= m; ++j) 67             if(ch[i][j] == .) 68                 make(i, j); 69     for(i = 1; i <= n; ++i){ 70         for(j = 1; j <= m; ++j){ 71             rt = fin(val[i][j]); 72             if(ch[i][j] == . && fin(val[0][0]) != rt){ 73                 if(vis[rt]) continue; 74                 else  vis[rt] = true; 75                 v.push_back(rt); 76             } 77         } 78     } 79     sort(v.begin(), v.end(), cmp); 80     int len = v.size(); 81     t = len; 82     int ans = 0; 83     if(t > k){ 84         for(i = 0; i < len; ++i){ 85             rt = fin(v[i]); 86             if(vis[rt]){ 87                 vis[rt] = false; 88                 t--; 89                 for(j = 1; j <= n; ++j) 90                     for(kk = 1; kk <= m; ++kk)//我第一遍把这里写成k导致WA死 91                         if(fin(val[j][kk]) == rt) {ch[j][kk] = *; ans++;} 92             } 93             if(t == k) break; 94         } 95     } 96     printf("%d\n", ans); 97     for(i = 1; i <= n; ++i){ 98         for(j = 1; j <= m; ++j) 99             printf("%c", ch[i][j]);100         puts("");101     }102     return 0;103 }
View Code

 

codeforces723 D. Lakes in Berland(并查集)