bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题，并查集or 二分+bfs验证连通性)
题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。
先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将把所有空的点以及china(设标号为n*m+1)点,和india(**设标号为n*m+2) **点通过并查集来合并..可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。 china点和india点特殊搞就好。
然后判断india和china是否联通，如果是则输出-1.否则从最后添加的山开始移除，每次移除一座山，添加四个方向能添加的边（注意这里不要忘记如果改点在第0行或者第n-1行还要添加和china或者india的边）
然后移除后询问india和china是否联通 （root(china)==root(india)?）
如果时间i联通了，而i+1没有联通，说明时间i是两国最早的失去联系的时间。
第一次做这种题目，这种题目的一般做法都是倒过来做。貌似还有一个二分删除的山+bfs判断连通性的。。。？ 窝再搞搞看。 update :二分+bfs判断连通性。其实这个思路更常规。。做法就是字面意思。注意无解的判断即可。
并查集解法：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月27日 星期日 20时11分02秒
4File Name :code/bc/#77/1003.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=505;
34char maze[N][N];
35int f[N*N];
36int n,m;
37int q;
38int p[N][N];
39int china;
40int india;
41struct node
42{
43 int x,y;
44 int id;
45
46}shan[N*N],kong[N*N];
47
48int root ( int x)
49{
50 if (x!=f[x]) f[x] = root (f[x]);
51 return f[x];
52}
53
54void merge( int x,int y)
55{
56 int rx = root (x);
57 int ry = root (y);
58// cout<<"rx::"<<rx<<" ry::"<<ry<<endl;
59 if (rx!=ry)
60 {
61 f[rx] = ry ;
62// f[ry] = rx;
63 }
64}
65
66void addegg( int x,int y)
67{
68 if (x-1>=0&&maze[x-1][y]=='0') merge(p[x][y],p[x-1][y]);
69 if (x+1<n&&maze[x+1][y]=='0') merge(p[x][y],p[x+1][y]);
70 if (y-1>=0&&maze[x][y-1]=='0') merge(p[x][y],p[x][y-1]);
71 if (y+1<m&&maze[x][y+1]=='0') merge(p[x][y],p[x][y+1]);
72
73 if (x==0) merge(p[x][y],china); //一开始忘记更新边缘的山被移除后，点和china以及india的边了。
74 if (x==n-1) merge(p[x][y],india);
75}
76int main()
77{
78 #ifndef ONLINE_JUDGE
79 freopen("code/in.txt","r",stdin);
80 #endif
81
82 int T;
83 cin>>T;
84 while (T--)
85 {
86 scanf("%d %d",&n,&m);
87 for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
88
89 scanf("%d",&q);
90 for ( int i = 1 ; i <= q ; i++)
91 {
92 int x,y;
93 scanf("%d %d",&x,&y);
94 shan[i].x = x;
95 shan[i].y = y;
96 shan[i].id = i;
97// maze[x][y] = '1'; //先统计空位。
98 }
99
100 int cnt = 0 ;
101 ms(p,-1);
102 for ( int i = 0 ; i < n ; i++)
103 {
104 for ( int j = 0 ; j < m; j++)
105 {
106 if (maze[i][j]=='0')
107 {
108 cnt++;
109 kong[cnt].x = i ;
110 kong[cnt].y = j;
111 kong[cnt].id = i;
112 p[i][j] = cnt;
113 }
114 }
115 }
116
117 for ( int i = 1 ; i <= q ; i ++)
118 {
119 int x = shan[i].x;
120 int y = shan[i].y;
121 maze[x][y]='1';
122 }
123 //check kong...ok!
124 //for ( int i = 1 ; i <= cnt ; i++) cout<<"kong:"<<kong[i].x<<" "<<kong[i].y<<endl;
125
126 china = n*m+1;
127 india = n*m+2;
128 for ( int i = 0 ; i <= n*m+2 ; i++) f[i] = i;
129 // f[china] = china;
130 // f[india] = india;
131 // cout<<"china:"<<china<<endl;
132 // cout<<"india:"<<india<<endl;
133 for ( int j = 0 ; j < m ; j++)
134 {
135 if (maze[0][j]=='0')
136 {
137 merge(china,p[0][j]);
138 }
139 if (maze[n-1][j]=='0')
140 {
141 merge(india,p[n-1][j]);
142 }
143 }
144
145 for ( int i = 0 ;i < n ; i++)
146 {
147 for ( int j = 0 ; j < m ; j ++)
148 {
149 if (maze[i][j]=='1') continue;
150 if (maze[i-1][j]=='0') merge(p[i-1][j],p[i][j]);
151 if (maze[i][j-1]=='0') merge(p[i][j-1],p[i][j]);
152 }
153 }
154
155 if (root(china)==root(india))
156 {
157 puts("-1");
158 continue;
159 }
160
161 for ( int i = q ; i >= 1 ; i--)
162 {
163 int x = shan[i].x;
164 int y = shan[i].y;
165
166 maze[x][y] = '0';
167 addegg(x,y);
168 if (root(china)==root(india))
169 {
170 printf("%d\n",i);
171 break;
172 }
173 }
174 }
175
176 #ifndef ONLINE_JUDGE
177 fclose(stdin);
178 #endif
179 return 0;
180}
二分+bfs判断连通性。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年03月28日 星期一 21时12分05秒
4File Name :code/hdu/5652.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=501;
34char maze[N][N];
35int n,m;
36int q;
37bool vis[N][N];
38
39struct node
40{
41 int x,y;
42
43 bool ok ()
44 {
45 if (x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]) return true;
46 return false;
47 }
48}shan[250005];
49
50
51int check( int id)
52{
53
54 for ( int i = 0 ; i < n ; i++)
55 {
56 for ( int j = 0 ; j < m ; j ++)
57 {
58 if (maze[i][j]=='1') vis[i][j] = true;
59 else vis[i][j] = false;
60 }
61 }
62
63 for ( int i = 1 ; i <= id ; i++)
64 {
65 int x = shan[i].x;
66 int y = shan[i].y;
67 vis[x][y] = true;
68 }
69
70 queue<node>q;
71 for ( int j = 0 ; j < m ; j++)
72 {
73
74 if (!vis[0][j])
75 {
76 node tmp;
77 tmp.x = 0;
78 tmp.y = j;
79 q.push(tmp);
80 }
81 }
82
83 while (!q.empty())
84 {
85 node pre = q.front();q.pop();
86 if (pre.x==n-1) return 1;
87 for ( int i = 0 ; i < 4 ; i++)
88 {
89 node nxt;
90 nxt.x = pre.x + dx4[i];
91 nxt.y = pre.y + dy4[i];
92 if (nxt.ok())
93 {
94 vis[nxt.x][nxt.y] = true;
95 q.push(nxt);
96
97 }
98 }
99 }
100 return 0;
101}
102
103int bin()
104{
105 int l = 1 ;
106 int r = q ;
107 int mid;
108 while (l<=r)
109 {
110 mid = (l+r)/2;
111 if (check(mid))
112 l = mid + 1;
113 else r = mid -1;
114 }
115 if (l>q) return -1;
116 return l;
117}
118int main()
119{
120 #ifndef ONLINE_JUDGE
121 freopen("code/in.txt","r",stdin);
122 #endif
123
124 int T;
125 cin>>T;
126 while (T--)
127 {
128 scanf("%d%d",&n,&m);
129 for ( int i = 0 ; i < n; i++) scanf("%s",maze[i]);
130 scanf("%d",&q);
131 for ( int i = 1 ; i <= q ; i ++) scanf("%d %d",&shan[i].x,&shan[i].y);
132 int ans = bin();
133 printf("%d\n",ans);
134 }
135
136 #ifndef ONLINE_JUDGE
137 fclose(stdin);
138 #endif
139 return 0;
140}