任意门：http://poj.org/problem?id=1984
Navigation Nightmare
| Time Limit: 2000MS | Memory Limit: 30000K | |
| Total Submissions: 7783 | Accepted: 2801 | |
| Case Time Limit: 1000MS | ||
Description
Farmer John‘s pastoral neighborhood has N farms (2 <= N <= 40,000), usually numbered/labeled 1..N. A series of M (1 <= M < 40,000) vertical and horizontal roads each of varying lengths (1 <= length <= 1000) connect the farms. A map of these farms might look something like the illustration below in which farms are labeled F1..F7 for clarity and lengths between connected farms are shown as (n):
Being an ASCII diagram, it is not precisely to scale, of course.
Each farm can connect directly to at most four other farms via roads that lead exactly north, south, east, and/or west. Moreover, farms are only located at the endpoints of roads, and some farm can be found at every endpoint of every road. No two roads cross, and precisely one path
(sequence of roads) links every pair of farms.
FJ lost his paper copy of the farm map and he wants to reconstruct it from backup information on his computer. This data contains lines like the following, one for every road:
There is a road of length 10 running north from Farm #23 to Farm #17
There is a road of length 7 running east from Farm #1 to Farm #17
...
As FJ is retrieving this data, he is occasionally interrupted by questions such as the following that he receives from his navigationally-challenged neighbor, farmer Bob:
What is the Manhattan distance between farms #1 and #23?
FJ answers Bob, when he can (sometimes he doesn‘t yet have enough data yet). In the example above, the answer would be 17, since Bob wants to know the "Manhattan" distance between the pair of farms.
The Manhattan distance between two points (x1,y1) and (x2,y2) is just |x1-x2| + |y1-y2| (which is the distance a taxicab in a large city must travel over city streets in a perfect grid to connect two x,y points).
When Bob asks about a particular pair of farms, FJ might not yet have enough information to deduce the distance between them; in this case, FJ apologizes profusely and replies with "-1".
??????????F1 --- (13) ---- F6 --- (9) ----- F3
???????????| ????????????????????????????????|
??????????(3) ???????????????????????????????|
???????????| ???????????????????????????????(7)
??????????F4 --- (20) -------- F2 ???????????|
???????????| ????????????????????????????????|
??????????(2) ??????????????????????????????F5
???????????|
??????????F7
Being an ASCII diagram, it is not precisely to scale, of course.
Each farm can connect directly to at most four other farms via roads that lead exactly north, south, east, and/or west. Moreover, farms are only located at the endpoints of roads, and some farm can be found at every endpoint of every road. No two roads cross, and precisely one path
(sequence of roads) links every pair of farms.
FJ lost his paper copy of the farm map and he wants to reconstruct it from backup information on his computer. This data contains lines like the following, one for every road:
There is a road of length 10 running north from Farm #23 to Farm #17
There is a road of length 7 running east from Farm #1 to Farm #17
...
As FJ is retrieving this data, he is occasionally interrupted by questions such as the following that he receives from his navigationally-challenged neighbor, farmer Bob:
What is the Manhattan distance between farms #1 and #23?
FJ answers Bob, when he can (sometimes he doesn‘t yet have enough data yet). In the example above, the answer would be 17, since Bob wants to know the "Manhattan" distance between the pair of farms.
The Manhattan distance between two points (x1,y1) and (x2,y2) is just |x1-x2| + |y1-y2| (which is the distance a taxicab in a large city must travel over city streets in a perfect grid to connect two x,y points).
When Bob asks about a particular pair of farms, FJ might not yet have enough information to deduce the distance between them; in this case, FJ apologizes profusely and replies with "-1".
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains four space-separated entities, F1,
???????F2, L, and D that describe a road. F1 and F2 are numbers of
???????two farms connected by a road, L is its length, and D is a
???????character that is either ‘N‘, ‘E‘, ‘S‘, or ‘W‘ giving the
???????direction of the road from F1 to F2.
* Line M+2: A single integer, K (1 <= K <= 10,000), the number of FB‘s
???????queries
* Lines M+3..M+K+2: Each line corresponds to a query from Farmer Bob
???????and contains three space-separated integers: F1, F2, and I. F1
???????and F2 are numbers of the two farms in the query and I is the
???????index (1 <= I <= M) in the data after which Bob asks the
???????query. Data index 1 is on line 2 of the input data, and so on.
Output
* Lines 1..K: One integer per line, the response to each of Bob‘s
???????queries. ?Each line should contain either a distance
???????measurement or -1, if it is impossible to determine the
???????appropriate distance.
Sample Input
7 61 6 13 E6 3 9 E3 5 7 S4 1 3 N2 4 20 W4 7 2 S31 6 11 4 32 6 6
Sample Output
13-110
Hint
At time 1, FJ knows the distance between 1 and 6 is 13.
At time 3, the distance between 1 and 4 is still unknown.
At the end, location 6 is 3 units west and 7 north of 2, so the distance is 10.
At time 3, the distance between 1 and 4 is still unknown.
At the end, location 6 is 3 units west and 7 north of 2, so the distance is 10.
?题意概括：
给出 M 个建树的操作，K 次查询，每次查询 x 到 y 经过前 num 次建树操作的距离，如果未联通则输出-1；
解题思路：
带权并查集，路径压缩采用向量法。
dx【i】表示 i 距离所在树根结点的横坐标
dy【i】表示 i 距离所在树根结点的纵坐标
合并 u v 过程：
先合并两棵子树
ru = getfa（u）
rv = getfa（v）
改变其中一棵子树的根结点
fa[ rv ] = ru;
更新根结点的相对值（之后子树的相对值会通过查找父结点的过程进行更新）
dx[ rv ] = dx[ u ] - dx[ v ] - wx[ u, v];
dy[ rv ] = dy[ u ] - dy[ v ] - wy[ u, v];
先执行num次建树操作
查找父结点的同时压缩路径
查询最后结果
如果相同根，直接计算两点的曼哈顿距离
否则不连通
Tip：
题目没有说查询的 num 是非递减有序的，所以处理查询前要对 num 进行排序！！！
也就是说离线处理，在线处理会出错。（虽然poj上的数据我没有排序也AC了， 但这是需要考虑的情况）
AC code：
1 //离线带权并查集 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 #include <cstring> 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 const int MAXN = 4e4+5; 9 const int MAXK = 1e4+10;10 struct Query{int x, y, index, no;}q[MAXN]; ?//查询信息11 int fa[MAXN], dx[MAXN], dy[MAXN]; ??//并查集，路径压缩（距离起点的横坐标距离 和 纵坐标距离）12 int u[MAXN], v[MAXN]; ??????????????//第i个操作的起点 和 终点13 int ans[MAXK]; ???//第 k 次查询的结果14 int wx[MAXN], wy[MAXN]; ????????????//wx[ i ] 第i个操作的横坐标边权 wy[ i ] 第i个操作的纵坐标边权15 int N, M, K;16 17 void init()18 {19 ????for(int i = 0; i <= N; i++){20 ????????fa[i] = i;21 ????????dx[i] = 0;22 ????????dy[i] = 0;23 ????}24 ????memset(q, 0, sizeof(q));25 }26 int aabs(int x){return x>0?x:-x;}27 int getfa(int s)28 {29 ????if(s == fa[s]) return s;30 ????int t = fa[s];31 ????fa[s] = getfa(fa[s]); ???//压缩路径32 ????dx[s] += dx[t];33 ????dy[s] += dy[t];34 ????return fa[s];35 }36 bool cmp(Query q1,Query q2){return q1.index < q2.index;}37 int main()38 {39 ????while(~scanf("%d%d", &N, &M)){40 ????????//scanf("%d%d", &N, &M);41 ????????init();42 ????????char nod;43 ????????for(int i = 1, d; i <= M; i++){44 ????????????scanf("%d%d%d %c", &u[i], &v[i], &d, &nod);45 ????????????if(nod == ‘E‘) {wx[i] = d; wy[i] = 0;}46 ????????????else if(nod == ‘W‘) {wx[i] = -d; wy[i] = 0;}47 ????????????else if(nod == ‘N‘) {wy[i] = d; wx[i] = 0;}48 ????????????else if(nod == ‘S‘) {wy[i] = -d; wx[i] = 0;}49 ????????}50 ????????scanf("%d", &K);51 ????????for(int i = 1; i <= K; i++){52 ????????????scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].index);53 ????????????q[i].no = i;54 ????????}55 ????????sort(q+1, q+K+1, cmp);56 ????????int k = 1;57 ????????for(int i = 1; i <= K; i++){58 ????????????//printf("i:%d\n", i);59 ????????????while(k <= q[i].index){ ????????????????//合并index个操作60 ????????????????//printf("k:%d\n", k);61 ????????????????int ru = getfa(u[k]);62 ????????????????int rv = getfa(v[k]);63 ????????????????//printf("u:%d ru:%d v:%d rv:%d\n", u[k], ru, v[k], rv);64 ????????????????fa[rv] = ru; ???????????????????????????//合并两个集合65 ????????????????dx[rv] = dx[u[k]] - dx[v[k]] - wx[k]; ??//66 ????????????????dy[rv] = dy[u[k]] - dy[v[k]] - wy[k];67 ????????????????k++;68 ????????????????}69 ????????????//printf("k:%d\n", k);70 ????????????if(getfa(q[i].x) != getfa(q[i].y)) ans[q[i].no] = -1; ?//两点经过index次操作后还是没有相连71 ????????????else{72 ????????????????ans[q[i].no] = aabs(dx[q[i].x] - dx[q[i].y]) + aabs(dy[q[i].x] - dy[q[i].y]);73 ????????????}74 ????????????//puts("");75 ????????}76 ????????for(int it = 1; it <= K; it++) printf("%d\n", ans[it]);77 ????}78 ????return 0;79 }一道拖了好久好久的带权并查集，给几个数据纪念一下
?1 Input: ?2 8 7 ?3 1 2 1 S ?4 3 4 5 S ?5 5 6 8 S ?6 7 8 2 S ?7 3 2 3 N ?8 7 6 13 N ?9 5 4 7 N 10 6 11 1 3 1 12 1 4 5 13 3 4 2 14 4 5 7 15 1 8 6 16 1 8 7 17 ?18 Output: 19 -1 20 9 21 5 22 7 23 -1 24 39 25 ?26 Input: 27 100 99 28 1 2 1000 E 29 2 3 1000 E 30 3 4 1000 E 31 4 5 1000 E 32 5 6 1000 E 33 6 7 1000 E 34 7 8 1000 E 35 8 9 1000 E 36 9 10 1000 E 37 10 11 1000 E 38 11 12 1000 E 39 12 13 1000 E 40 13 14 1000 E 41 14 15 1000 E 42 15 16 1000 E 43 16 17 1000 E 44 17 18 1000 E 45 18 19 1000 E 46 19 20 1000 E 47 20 21 1000 E 48 21 22 1000 E 49 22 23 1000 E 50 23 24 1000 E 51 24 25 1000 E 52 26 27 1000 E 53 27 28 1000 E 54 28 29 1000 E 55 29 30 1000 E 56 30 31 1000 E 57 31 32 1000 E 58 32 33 1000 E 59 33 34 1000 E 60 34 35 1000 E 61 35 36 1000 E 62 36 37 1000 E 63 37 38 1000 E 64 38 39 1000 E 65 39 40 1000 E 66 40 41 1000 E 67 41 42 1000 E 68 42 43 1000 E 69 43 44 1000 E 70 44 45 1000 E 71 45 46 1000 E 72 46 47 1000 E 73 47 48 1000 E 74 48 49 1000 E 75 49 50 1000 E 76 51 52 1000 E 77 52 53 1000 E 78 53 54 1000 E 79 54 55 1000 E 80 55 56 1000 E 81 56 57 1000 E 82 57 58 1000 E 83 58 59 1000 E 84 59 60 1000 E 85 60 61 1000 E 86 61 62 1000 E 87 62 63 1000 E 88 63 64 1000 E 89 64 65 1000 E 90 65 66 1000 E 91 66 67 1000 E 92 67 68 1000 E 93 68 69 1000 E 94 69 70 1000 E 95 70 71 1000 E 96 71 72 1000 E 97 72 73 1000 E 98 73 74 1000 E 99 74 75 1000 E100 76 77 1000 E101 77 78 1000 E102 78 79 1000 E103 79 80 1000 E104 80 81 1000 E105 81 82 1000 E106 82 83 1000 E107 83 84 1000 E108 84 85 1000 E109 85 86 1000 E110 86 87 1000 E111 87 88 1000 E112 88 89 1000 E113 89 90 1000 E114 90 91 1000 E115 91 92 1000 E116 92 93 1000 E117 93 94 1000 E118 94 95 1000 E119 95 96 1000 E120 96 97 1000 E121 97 98 1000 E122 98 99 1000 E123 99 100 1000 E124 10 40 100 S125 30 60 100 S126 70 90 100 S127 100128 34 44 96129 55 65 96130 38 48 96131 63 73 96132 2 12 96133 76 86 96134 1 11 96135 62 72 96136 8 18 96137 41 51 96138 58 68 96139 60 70 96140 30 40 96141 67 77 96142 60 70 96143 74 84 96144 80 90 96145 11 21 96146 21 31 96147 87 97 96148 33 43 96149 20 30 96150 83 93 96151 35 45 96152 56 66 96153 32 42 96154 44 54 96155 36 46 96156 69 79 96157 74 84 96158 51 61 96159 64 74 96160 38 48 96161 89 99 96162 37 47 96163 40 50 96164 36 46 96165 89 99 96166 11 21 96167 5 15 96168 39 49 96169 30 40 96170 64 74 96171 30 40 96172 58 68 96173 33 43 96174 14 24 96175 10 20 96176 43 53 96177 86 96 96178 6 16 96179 37 47 96180 67 77 96181 51 61 96182 33 43 96183 32 42 96184 82 92 96185 77 87 96186 30 40 96187 60 70 96188 22 32 96189 80 90 96190 34 44 96191 60 70 96192 40 50 96193 32 42 96194 61 71 96195 75 85 96196 82 92 96197 33 43 96198 80 90 96199 83 93 96200 25 35 96201 15 25 96202 22 32 96203 44 54 96204 48 58 96205 35 45 96206 53 63 96207 52 62 96208 82 92 96209 59 69 96210 51 61 96211 59 69 96212 71 81 96213 83 93 96214 90 100 96215 62 72 96216 31 41 96217 29 39 96218 84 94 96219 53 63 96220 71 81 96221 79 89 96222 22 32 96223 20 30 96224 72 82 96225 44 54 96226 5 15 96227 63 73 96228 229 Output:230 10000231 10000232 10000233 10000234 10000235 10000236 10000237 10000238 10000239 -1240 10000241 10000242 10000243 -1244 10000245 -1246 10000247 10000248 -1249 10000250 10000251 -1252 10000253 10000254 10000255 10000256 -1257 10000258 -1259 -1260 10000261 10000262 10000263 10000264 10000265 10000266 10000267 10000268 10000269 10000270 10000271 10000272 10000273 10000274 10000275 10000276 10000277 10000278 -1279 10000280 10000281 10000282 -1283 10000284 10000285 10000286 10000287 10000288 10000289 10000290 -1291 10000292 10000293 10000294 10000295 10000296 10000297 -1298 10000299 10000300 10000301 10000302 -1303 10000304 -1305 -1306 -1307 10000308 10000309 10000310 10000311 10000312 10000313 10000314 -1315 10000316 10000317 10000318 10000319 10000320 10000321 10000322 -1323 10000324 -1325 -1326 -1327 -1328 10000329 10000
小蒟蒻不才，如有错误，欢迎大佬们指正~
POJ 1984 Navigation Nightmare 【经典带权并查集】
原文地址：https://www.cnblogs.com/ymzjj/p/9780359.html