hdu 5652 India and China Origins（二分+bfs || 并查集）BestCoder Round #77 (div.2)

题意：

给一个n*m的矩阵作为地图，0为通路，1为阻碍。只能向上下左右四个方向走。每一年会在一个通路上长出一个阻碍，求第几年最上面一行与最下面一行会被隔开。

输入：

首行一个整数t，表示共有t组数据。

每组数据首行两个整数n, m，表示矩阵大小。

接下来输入矩阵。

接下来输入一个整数q，表示一共q年。

接下来q行，第i行为两个整数xi, yi，表示在第i年会在xi, yi长出一个阻碍。数据保证只会在通路上生成阻碍。

输出：

如果在第i年被隔开，则输出i。如果始终无法隔开，则输出-1。

吐槽：

我刚开始一看n和m是500，q是n*m，然后判断数据范围是500^3，然后果断判断暴力bfs能过，直接开干，小数据还真过了T_T，结果终测跪了Orz。后来发现其实数据范围是500^4→_→，也就是n*m*q。觉得二分+bfs能过。结果别人说确实能过。然后我自己写了一下，顺利过了。但二分还是写的不熟，中间出了点小差错=_=。

看题解标程居然是并查集，果断给跪，这么吊的思路也是没谁了，而且实现起来也是非常简单的并查集。直接套模板都可以的那种。亏我还专门搞过一段时间的并查集呢，思路还是不够宽广啊，以后脑洞要更大一点才行。嗯，就这么愉快地决定了。

题解：

二分+bfs。很好理解，将第一行入队，然后bfs向上下左右瞎jb搜，只要能够搜到最后一行，就表示没有隔开（反之亦然）。二分年限即可。时间复杂度O(n*m*log2(q))；
离线并查集，将所有的q保存下来，然后生成最终地图。然后建立初始并查集，将每个通路和它上下左右四个通路连接，创建两个虚节点s1, t1，将第一行所有点连接到s1，将最后一行所有点连接到t1。然后从第q年往回减阻碍，每减一个阻碍就将这个点与它周围所存在的通路合并，直到将s1和t1合并到同一个集合里。然后输出此时的年限即可。时间复杂度为O(n*m+q)。

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 
  8 const int N = 510;
  9 
 10 struct Node
 11 {
 12     int x, y;
 13 };
 14 
 15 int dis[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};             //搜索的方向
 16 
 17 int t, n, m, q;
 18 char mp[N][N];                                                  //初始地图
 19 char s[N][N];                                                   //每次搜的地图
 20 bool vis[N][N];                                                 //记忆化剪枝
 21 Node ss[N*N];                                                   //记录（离线）生成出阻碍
 22 
 23 bool bfs(int x)                                                 //bfs瞎jb搜，能隔开返回0，连通则返回1
 24 {
 25     for(int i = 0; i < n; i++)
 26     {
 27         for(int j = 0; j < m; j++) s[i][j] = mp[i][j];
 28     }
 29     for(int i = 0; i < x; i++) s[ss[i].x][ss[i].y] = '1';
 30     queue<Node> que;
 31     memset(vis, 0, sizeof(vis));
 32     for(int i = 0; i < m; i++)
 33     {
 34         if(s[0][i] == '0')
 35         {
 36             Node p;
 37             p.x = 0;
 38             p.y = i;
 39             que.push(p);
 40             vis[0][i] = 1;
 41         }
 42     }
 43     while(!que.empty())
 44     {
 45         Node p = que.front();
 46         que.pop();
 47         Node pp;
 48         for(int i = 0; i < 4; i++)
 49         {
 50             int dx = p.x+dis[i][0];
 51             int dy = p.y+dis[i][1];
 52             if(dx >= 0 && dx < n && dy >= 0 && dy < m && s[dx][dy] == '0' && vis[dx][dy] == 0)
 53             {
 54                 if(dx == n-1) return 1;
 55                 pp.x = dx;
 56                 pp.y = dy;
 57                 que.push(pp);
 58                 vis[dx][dy] = 1;
 59             }
 60         }
 61     }
 62     return 0;
 63 }
 64 
 65 void Init()
 66 {
 67     scanf("%d%d", &n, &m);
 68     for(int i = 0; i < n; i++)
 69     {
 70         scanf("%s", mp[i]);
 71     }
 72     scanf("%d", &q);
 73     for(int i = 0; i < q; i++) scanf("%d%d", &ss[i].x, &ss[i].y);
 74 }
 75 
 76 void Work()
 77 {
 78     int l = 0, r = q-1;
 79     if(!bfs(l))                                                         //判断初始能否隔开
 80     {
 81         printf("0
");
 82         return;
 83     }
 84     if(bfs(r))                                                          //判断最终能否隔开
 85     {
 86         printf("-1
");
 87         return;
 88     }
 89     bool flag;
 90     while(l < r-1)                                                      //二分年限
 91     {
 92         int lr = (l+r)/2;
 93         flag = bfs(lr);
 94         if(flag) l = lr;
 95         else r = lr;
 96     }
 97     printf("%d
", r);
 98 }
 99 
100 int main()
101 {
102     scanf("%d", &t);
103     for(int tm = 1; tm <= t; tm++)
104     {
105         Init();
106         Work();
107     }
108     return 0;
109 }

二分+bfs

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int N = 510;
  8 
  9 int dis[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; //四个方向搜索
 10 
 11 int t;
 12 int n, m;
 13 int q;
 14 char mp[N][N];                                      //地图
 15 int s[N*N][2];                                      //记录（离线）生成的阻碍
 16 int fm[N*N];                                        //并查集
 17 int vis[N][N];                                      //dfs记忆化
 18 
 19 int mfind(int x)                                    //并查集查询
 20 {
 21     int fx = x;
 22     while(fx != fm[fx])
 23     {
 24         fx = fm[fx];
 25     }
 26     while(x != fx)
 27     {
 28         int mx = fm[x];
 29         fm[x] = fx;
 30         x = mx;
 31     }
 32     return fx;
 33 }
 34 
 35 void mmerge(int x, int y)                           //并查集合并
 36 {
 37     int fx = mfind(x);
 38     int fy = mfind(y);
 39     if(fx != fy) fm[fy] = fx;
 40 }
 41 
 42 void dfs(int x, int y)                              //遍历全图
 43 {
 44     int dx, dy;
 45     for(int i = 0; i < 4; i++)
 46     {
 47         dx = x+dis[i][0];
 48         dy = y+dis[i][1];
 49         if(dx >= 0 && dx < n && dy >= 0 && dy < m && mp[dx][dy] == '0' && !vis[dx][dy])
 50         {
 51             mmerge(x*m+y, dx*m+dy);
 52             vis[dx][dy] = 1;
 53             dfs(dx, dy);
 54         }
 55     }
 56 }
 57 
 58 void Init()
 59 {
 60     scanf("%d%d", &n, &m);
 61     for(int i = 0; i < n; i++) scanf("%s", mp[i]);
 62     scanf("%d", &q);
 63     for(int i = 0; i < q; i++)
 64     {
 65         scanf("%d%d", &s[i][0], &s[i][1]);
 66         mp[s[i][0]][s[i][1]] = '1';
 67     }
 68 }
 69 
 70 void Work()
 71 {
 72 
 73 
 74     for(int i = 0; i < n*m+2; i++) fm[i] = i;       //并查集预处理
 75     memset(vis, 0, sizeof(vis));                    //记忆化标记
 76     for(int i = 0; i < n; i++)                      //遍历全图，初始化并查集
 77     {
 78         for(int j = 0; j < m; j++)
 79         {
 80             if(!vis[i][j] && mp[i][j] == '0')
 81             {
 82                 vis[i][j] = 1;
 83                 dfs(i, j);
 84             }
 85         }
 86     }
 87 
 88     for(int i = 0; i < m; i++)                      //虚节点s1(n*m)与t1(n*m+1)的创建
 89     {
 90         mmerge(n*m, i);
 91         mmerge(n*m+1, (n-1)*m+i);
 92     }
 93     if(mfind(n*m+1) == mfind(n*m))                  //始终无法隔开
 94     {
 95         printf("-1
");
 96         return;
 97     }
 98 
 99     int p;                                          //第p+1年隔开
100     bool flag = 0;                                  //临时标记，退出循环的判断
101     for(p = q-1; p >= 0; p--)
102     {
103         int dx, dy;
104         int xx = s[p][0];
105         int yy = s[p][1];
106         mp[xx][yy] = '0';
107         for(int i = 0; i < 4; i++)
108         {
109             dx = xx+dis[i][0];
110             dy = yy+dis[i][1];
111             if(dx >= 0 && dx < n && dy >= 0 && dy < m && mp[dx][dy] == '0')
112             {
113                 mmerge(dx*m+dy, xx*m+yy);
114                 if(mfind(n*m+1) == mfind(n*m))
115                 {
116                     flag = 1;
117                     break;
118                 }
119             }
120         }
121         if(flag) break;
122     }
123     if(flag) printf("%d
", p+1);
124     else printf("0
");
125 }
126 
127 int main()
128 {
129     //freopen("test.in", "r", stdin);
130     scanf("%d", &t);
131     for(int tm = 1; tm <= t; tm++)
132     {
133         Init();
134         Work();
135     }
136 }

并查集