BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦
发布日期:2022-02-07 06:39:34
浏览次数:16
分类:技术文章
本文共 2182 字,大约阅读时间需要 7 分钟。
题目大意:自行脑补。
思路:维护两个维度上的带权并查集即可。
注意对于题目给出的一堆关系,我们应该添加两对关系。
Code:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using
namespace
std;
#define N 40010
int
n, m;
struct
UnionSet {
int
root[N], dis[N];
void
reset() {
int
i;
for
(i = 1; i <= n; ++i)
root[i] = i, dis[i] = 0;
}
int
find(
int
x) {
static
int
stack[N];
int
top = 0;
for
(; x != root[x]; x = root[x])
stack[++top] = x;
for
(
int
i = top - 1; i >= 1; --i)
dis[stack[i]] += dis[stack[i + 1]], root[stack[i]] = x;
return
x;
}
}Set[2];
#define K 10010
struct
Ask {
int
u, v, tclock, lab;
void
read(
int
_) {
lab = _;
scanf
(
"%d%d%d"
, &u, &v, &tclock);
}
bool
operator < (
const
Ask &B)
const
{
return
tclock < B.tclock;
}
}S[K];
int
ans[K];
#define M 40010
int
u[M], v[M], d[M];
bool
vec[M];
#define _abs(x) ((x)>0?(x):-(x))
int
main() {
#ifndef ONLINE_JUDGE
freopen
(
"tt.in"
,
"r"
, stdin);
#endif
scanf
(
"%d%d"
, &n, &m);
register
int
i, j;
int
a, b, x;
char
s[10];
for
(i = 1; i <= m; ++i) {
scanf
(
"%d%d%d%s"
, &a, &b, &x, s);
d[i] = x;
if
(s[0] ==
'E'
)
u[i] = a, v[i] = b, vec[i] = 0;
else
if
(s[0] ==
'W'
)
u[i] = b, v[i] = a, vec[i] = 0;
else
if
(s[0] ==
'N'
)
u[i] = a, v[i] = b, vec[i] = 1;
else
u[i] = b, v[i] = a, vec[i] = 1;
}
int
Q;
scanf
(
"%d"
, &Q);
for
(i = 1; i <= Q; ++i)
S[i].read(i);
sort(S + 1, S + Q + 1);
Set[0].reset(), Set[1].reset();
int
ra, rb;
j = 1;
for
(i = 1; i <= m; ++i) {
ra = Set[vec[i]].find(u[i]);
rb = Set[vec[i]].find(v[i]);
Set[vec[i]].root[ra] = rb;
Set[vec[i]].dis[ra] = d[i] + Set[vec[i]].dis[v[i]] - Set[vec[i]].dis[u[i]];
ra = Set[1 - vec[i]].find(u[i]);
rb = Set[1 - vec[i]].find(v[i]);
Set[1 - vec[i]].root[ra] = rb;
Set[1 - vec[i]].dis[ra] = Set[1 - vec[i]].dis[v[i]] - Set[1 - vec[i]].dis[u[i]];
for
(; S[j].tclock == i; ++j) {
ra = Set[0].find(S[j].u), rb = Set[0].find(S[j].v);
if
(ra != rb) {
ans[S[j].lab] = -1;
continue
;
}
ans[S[j].lab] += _abs(Set[0].dis[S[j].u] - Set[0].dis[S[j].v]);
ra = Set[1].find(S[j].u), rb = Set[1].find(S[j].v);
if
(ra != rb) {
ans[S[j].lab] = -1;
continue
;
}
ans[S[j].lab] += _abs(Set[1].dis[S[j].u] - Set[1].dis[S[j].v]);
}
}
for
(i = 1; i <= Q; ++i)
printf
(
"%d\n"
, ans[i]);
return
0;
}
转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/40347183 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月18日 04时31分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
”为什么有这么多人执着于中文编程?”回答两千赞留念及回应
2019-04-26
【家务】盘点小孩玩具零件缺失情况
2019-04-26
开发中文 API 的一些策略
2019-04-26
从日本编程书籍《我的第一本编程书》中译版看中文例程如何扬长避短——标识符(一)
2019-04-26
中文命名标识符如何区分类型和变量
2019-04-26
编程术语成系统中文化的意义
2019-04-26
草蟒 Python 中文 API 与 IDE 支持尝鲜
2019-04-26
一种改进中文 API 可读性的方法:参数不限于在末尾
2019-04-26
中文编程开发工具的生存模式探讨
2019-04-26
写给木兰编程语言研发团队的公开信
2019-04-26
为什么要急着为「木兰」编程语言贴上“造假”的标签?
2019-04-26
编程语言国产化的关键一战——对肆意污名化“木兰”编程语言说“不”
2019-04-26
各大媒体对「木兰」编程语言的不当言论盘点
2019-04-26
戳破针对「木兰」编程语言的拙劣谣言
2019-04-26
为「木兰」编程语言添加对中文命名标识符的支持
2019-04-26
悬赏万元,重现「木兰」编程语言编译器
2019-04-26
跳出编程语言本身看中文编程语言设计
2019-04-26
RPLY 入门例程中文化
2019-04-26