I - Navigation Nightmare——带权并查集

ゝ一世哀愁。 2022-06-12 12:44 155阅读 0赞

Think:  
1知识点：带权并查集+向量增移法  
2反思：变量初始化位置需要注意，避免重复计算

[vjudge题目链接][vjudge]

[建议参考博客][Link 1]

以下为Time Limit Exceeded代码——变量重复初始化，导致大量重复运算

/*
    1.带权并查集
    2.向量增移法
    */
    
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int N = 4e4 + 4e2;
    
    int n, m, k, f[N], x[N], y[N];
    char get[N][40];
    
    void Init();/*初始化*/
    int get_f(int v);/*寻找根节点并更新权值数组*/
    void Union(int a, int b, int dx, int dy);/*合并两个结点*/
    int dis(int x1, int x2, int y1, int y2);/*求曼哈顿距离*/
    
    int main(){
        int i, nd1, nd2, ct, cur, a, b, d, dx, dy;
        char st[4];
    
        scanf("%d %d", &n, &m);
        getchar();
    
        Init();
    
        for(i = 0; i < m; i++)
            gets(get[i]);
    
        scanf("%d", &k);
        while(k--){
            cur = 0;
    
            scanf("%d %d %d", &nd1, &nd2, &ct);
    
            for(i = cur; i < ct; i++){
                dx = 0, dy = 0;
                sscanf(get[i], "%d %d %d %s", &a, &b, &d, st);
                switch(st[0])
                {
                    case 'E': dx += d; break;
                    case 'W': dx -= d; break;
                    case 'N': dy += d; break;
                    case 'S': dy -= d; break;
                }
                Union(a, b, dx, dy);
            }
            cur = ct;
    
            int r1 = get_f(nd1);
            int r2 = get_f(nd2);
            if(r1 != r2)
                printf("-1\n");
            else
                printf("%d\n", dis(x[nd1], x[nd2], y[nd1], y[nd2]));
        }
        return 0;
    }
    void Init(){
        for(int i = 0; i <= n; i++){
            f[i] = i, x[i] = y[i] = 0;
        }
    }
    void Union(int a, int b, int dx, int dy){
        int r1 = get_f(a);
        int r2 = get_f(b);
        if(r1 != r2){
            f[r2] = r1;
            x[r2] = x[a] + dx - x[b];/*向量增移*/
            y[r2] = y[a] + dy - y[b];/*向量增移*/
        }
    }
    int get_f(int v){
        if(f[v] == v)
            return v;
        int tmp = f[v];
        f[v] = get_f(f[v]);
        x[v] += x[tmp];/*更新权值数组*/
        y[v] += y[tmp];/*更新权值数组*/
        return f[v];
    }
    int dis(int x1, int x2, int y1, int y2){
        return abs(x1-x2) + abs(y1-y2);
    }

以下为Accepted代码

/*
    1.带权并查集
    2.向量增移法
    */
    
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const int N = 4e4 + 4e2;
    
    int n, m, k, f[N], x[N], y[N];
    char get[N][40];
    
    void Init();/*初始化*/
    int get_f(int v);/*寻找根节点并更新权值数组*/
    void Union(int a, int b, int dx, int dy);/*合并两个结点*/
    int dis(int x1, int x2, int y1, int y2);/*求曼哈顿距离*/
    
    int main(){
        int i, nd1, nd2, ct, cur, a, b, d, dx, dy;
        char st[4];
    
        scanf("%d %d", &n, &m);
        getchar();
    
        Init();
    
        for(i = 0; i < m; i++)
            gets(get[i]);
    
        scanf("%d", &k);
    
        cur = 0;
        while(k--){
    
            scanf("%d %d %d", &nd1, &nd2, &ct);
    
            for(i = cur; i < ct; i++){
                dx = 0, dy = 0;
                sscanf(get[i], "%d %d %d %s", &a, &b, &d, st);
                switch(st[0])
                {
                    case 'E': dx += d; break;
                    case 'W': dx -= d; break;
                    case 'N': dy += d; break;
                    case 'S': dy -= d; break;
                }
                Union(a, b, dx, dy);
            }
            cur = ct;
    
            int r1 = get_f(nd1);
            int r2 = get_f(nd2);
            if(r1 != r2)
                printf("-1\n");
            else
                printf("%d\n", dis(x[nd1], x[nd2], y[nd1], y[nd2]));
        }
        return 0;
    }
    void Init(){
        for(int i = 0; i <= n; i++){
            f[i] = i, x[i] = y[i] = 0;
        }
    }
    void Union(int a, int b, int dx, int dy){
        int r1 = get_f(a);
        int r2 = get_f(b);
        if(r1 != r2){
            f[r2] = r1;
            x[r2] = x[a] + dx - x[b];/*向量增移*/
            y[r2] = y[a] + dy - y[b];/*向量增移*/
        }
    }
    int get_f(int v){
        if(f[v] == v)
            return v;
        int tmp = f[v];
        f[v] = get_f(f[v]);
        x[v] += x[tmp];/*更新权值数组*/
        y[v] += y[tmp];/*更新权值数组*/
        return f[v];
    }
    int dis(int x1, int x2, int y1, int y2){
        return abs(x1-x2) + abs(y1-y2);
    }

[vjudge]: https://vjudge.net/contest/163007#problem/I
[Link 1]: http://blog.csdn.net/tc_to_top/article/details/43447727