[POJ1984]Navigation Nightmare
试题描述
F1 --- (13) ---- F6 --- (9) ----- F3
| |
(3) |
| (7)
F4 --- (20) -------- F2 |
| |
(2) F5
|
F7
输入
* 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.
输出
* 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.
输入示例
7 6 1 6 13 E 6 3 9 E 3 5 7 S 4 1 3 N 2 4 20 W 4 7 2 S 3 1 6 1 1 4 3 2 6 6
输出示例
13 -1 10
数据规模及约定
见“试题描述”
题解
带权并查集，把每个关系中的位移转换成向量，然后这些向量是可以叠加的，于是就像子树权值加那样打一下懒标记搞一搞就好了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
return x * f;
}
struct Vector {
int x, y;
Vector() {}
Vector(int _, int __): x(_), y(__) {}
Vector operator + (const Vector& t) const { return Vector(x + t.x, y + t.y); }
Vector operator += (const Vector& t) { *this = *this + t; return *this; }
Vector operator - (const Vector& t) const { return Vector(x - t.x, y - t.y); }
int dis() const { return abs(x) + abs(y); }
};
#define maxn 40010
#define maxq 10010
struct Que {
int u, v, k, id;
Que() {}
Que(int _1, int _2, int _3, int _4): u(_1), v(_2), k(_3), id(_4) {}
bool operator < (const Que& t) const { return k < t.k; }
} qs[maxq];
int ans[maxq];
struct Edge {
int f1, f2;
Vector Mov;
Edge() {}
Edge(int _1, int _2, Vector _3): f1(_1), f2(_2), Mov(_3) {}
} es[maxn];
int fa[maxn];
Vector tag[maxn];
int findset(int x) {
if(x == fa[x]) return x;
int t = findset(fa[x]);
tag[x] += tag[fa[x]];
return fa[x] = t;
}
int main() {
int n = read(), m = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read(), l = read();
char dir[2];
scanf("%s", dir);
Vector Mov;
if(dir[0] == ‘N‘) Mov = Vector(-l, 0);
if(dir[0] == ‘S‘) Mov = Vector(l, 0);
if(dir[0] == ‘W‘) Mov = Vector(0, -l);
if(dir[0] == ‘E‘) Mov = Vector(0, l);
es[i] = Edge(u, v, Mov);
}
int q = read();
for(int i = 1; i <= q; i++) {
int u = read(), v = read(), k = read();
qs[i] = Que(u, v, k, i);
}
sort(qs + 1, qs + q + 1);
for(int i = 1; i <= n; i++) fa[i] = i, tag[i] = Vector(0, 0);
for(int i = 1, j = 1; i <= q; i++) {
while(j <= m && j <= qs[i].k) {
int u = findset(es[j].f1), v = findset(es[j].f2);
if(u != v) {
tag[v] = tag[es[j].f1] + es[j].Mov - tag[es[j].f2];
fa[v] = u;
}
j++;
}
int u = findset(qs[i].u), v = findset(qs[i].v);
if(u != v) ans[qs[i].id] = -1;
else ans[qs[i].id] = (tag[qs[i].u] - tag[qs[i].v]).dis();
}
for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
return 0;
}
原文：http://www.cnblogs.com/xiao-ju-ruo-xjr/p/6389013.html