BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦-白红宇的个人博客

发布日期：2022-02-07 06:39:34 浏览次数：15 分类：技术文章

本文共 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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：BZOJ1930 [Shoi2003]pacman 吃豆豆费用流

下一篇：写在NOIP之前-蒟蒻我到底会什么

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！