首页 > 代码库 > BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦

BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦

2024-07-28 10:52:59   217人阅读

题目大意：自行脑补。


思路：维护两个维度上的带权并查集即可。

注意对于题目给出的一堆关系，我们应该添加两对关系。


Code:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
usingnamespace std;
 
#define N 40010
intn, m;
structUnionSet {
    introot[N], dis[N];
    voidreset() {
        inti;
        for(i = 1; i <= n; ++i)
            root[i] = i, dis[i] = 0;
    }
    intfind(intx) {
        staticint stack[N];
        inttop = 0;
        for(; x != root[x]; x = root[x])
            stack[++top] = x;
        for(inti = top - 1; i >= 1; --i)
            dis[stack[i]] += dis[stack[i + 1]], root[stack[i]] = x;
        returnx;
    }
}Set[2];
 
#define K 10010
structAsk {
    intu, v, tclock, lab;
    voidread(int_) {
        lab = _;
        scanf("%d%d%d", &u, &v, &tclock);
    }
    booloperator < (constAsk &B) const{
        returntclock < B.tclock;
    }
}S[K];
intans[K];
 
#define M 40010
intu[M], v[M], d[M];
boolvec[M];
 
#define _abs(x) ((x)>0?(x):-(x))
 
intmain() {
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r", stdin);
    #endif
     
    scanf("%d%d", &n, &m);
     
    registerint i, j;
     
    inta, b, x;
    chars[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;
        elseif (s[0] == ‘W‘)
            u[i] = b, v[i] = a, vec[i] = 0;
        elseif (s[0] == ‘N‘)
            u[i] = a, v[i] = b, vec[i] = 1;
        else
            u[i] = b, v[i] = a, vec[i] = 1;
    }
     
    intQ;
    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();
     
    intra, 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]);
     
    return0;
}

BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦


联系
我们