HDU 2586 How far away ？ (LCA，Tarjan， spfa)

2021-11-18 18:04:22

题意：给定N个节点一棵树，现在要求询问任意两点之间的简单路径的距离，其实也就是最短路径距离。

析：用LCA问题的Tarjan算法，利用并查集的优越性，产生把所有的点都储存下来，然后把所有的询问也储存下来，然后从树根开始搜索这棵树，

在搜索子树的时候，把并查集的父结点不断更新，在搜索时计算答案，d[i] 表示从根结点到 i 结点的距离，然后分别计算到两个结点的距离，

再减去2倍的根结点到他们公共最近的结点距离，就OK了。不过这个题有个坑人的地方，不用输出那个空行，否则就是PE。

因为这个题询问比较少，所以我们可以用spfa来做。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 4e4 + 5;

const int mod = 1e9 + 7;

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline int Min(int a, int b){ return a < b ? a : b; }

inline int Max(int a, int b){ return a > b ? a : b; }

inline LL Min(LL a, LL b){ return a < b ? a : b; }

inline LL Max(LL a, LL b){ return a > b ? a : b; }

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

struct Edge{

    int to, w, next;

};

struct node{

    int to, id, next;

};

Edge a[maxn<<1];

node b[405];

int p[maxn], head[maxn<<1], cnt, cnt1, head1[maxn];

int rec[205][3], d[maxn];

bool vis[maxn];

int Find(int x){  return x == p[x] ? x : p[x] = Find(p[x]); }

void add(int u, int v, int w){

    a[cnt].to = v;

    a[cnt].w = w;

    a[cnt].next = head[u];

    head[u] = cnt++;

}

void add1(int u, int v, int id){

    b[cnt1].to = v;

    b[cnt1].id = id;

    b[cnt1].next = head1[u];

    head1[u] = cnt1++;

}

void Tarjan(int u){

    vis[u] = true;

    for(int i = head1[u]; ~i; i = b[i].next){

        int v = b[i].to;

        if(vis[v])  rec[b[i].id][2] = Find(v);

    }

    for(int i = head[u]; ~i; i = a[i].next){

        int v = a[i].to;

        if(!vis[v]){

            d[v] = d[u] + a[i].w;

            Tarjan(v);

            p[v] = u;

        }

    }

}

int main(){

    int T;  cin >> T;

    while(T--){

        scanf("%d %d", &n, &m);

        for(int i = 0; i <= n; ++i)  p[i] = i;

        int u, v, w;

        cnt = cnt1 = 0;

        memset(head, -1, sizeof head);

        memset(head1, -1, sizeof head1);

        for(int i = 1; i < n; ++i){

            scanf("%d %d %d", &u, &v, &w);

            add(u, v, w);

            add(v, u, w);

        }

        for(int i = 0; i < m; ++i){

            scanf("%d %d", &u, &v);

            add1(u, v, i);

            add1(v, u, i);

            rec[i][0] = u;

            rec[i][1] = v;

        }

        memset(vis, false, sizeof vis);

        d[1] = 0;

        Tarjan(1);

        for(int i = 0; i < m; ++i)

            printf("%d\n", d[rec[i][0]] + d[rec[i][1]] - 2*d[rec[i][2]]);

        //printf("\n");

    }

    return 0;

}

第二种写法：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 4e4 + 5;

const int mod = 1e9 + 7;

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline int Min(int a, int b){ return a < b ? a : b; }

inline int Max(int a, int b){ return a > b ? a : b; }

inline LL Min(LL a, LL b){ return a < b ? a : b; }

inline LL Max(LL a, LL b){ return a > b ? a : b; }

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

vector<int> G[maxn], w[maxn], q[maxn], id[maxn];

int d[maxn], p[maxn], ans[205];

bool vis[maxn];

int Find(int x){  return x == p[x] ? x : p[x] = Find(p[x]); }

void Tarjan(int u){

    vis[u] = true;

    for(int i = 0; i < G[u].size(); ++i){

        int v = G[u][i];

        if(!vis[v]){

            d[v] = d[u] + w[u][i];

            Tarjan(v);

            p[v] = u;

        }

    }

    for(int i = 0; i < q[u].size(); ++i){

        int v = q[u][i];

        if(vis[v])  ans[id[u][i]] = d[u] + d[v] - 2*d[Find(v)];

    }

}

int main(){

    int T;;  cin >> T;

    while(T--){

        scanf("%d %d", &n, &m);

        for(int i = 1; i <= n; ++i) G[i].clear(), w[i].clear(), q[i].clear(), id[i].clear(), p[i] = i;

        int u, v, val;

        for(int i = 1; i < n; ++i){

            scanf("%d %d %d", &u, &v, &val);

            G[u].push_back(v);

            G[v].push_back(u);

            w[u].push_back(val);

            w[v].push_back(val);

        }

        for(int i = 0; i < m; ++i){

            scanf("%d %d", &u, &v);

            q[u].push_back(v);

            q[v].push_back(u);

            id[u].push_back(i);

            id[v].push_back(i);

        }

        memset(vis, false, sizeof vis);

        d[1] = 0;

        Tarjan(1);

        for(int i = 0; i < m; ++i)

            printf("%d\n", ans[i]);

    }

    return 0;

}

spfa:

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 4e4 + 5;

const int mod = 1e9 + 7;

const int dr[] = {-1, 0, 1, 0};

const int dc[] = {0, 1, 0, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline int Min(int a, int b){ return a < b ? a : b; }

inline int Max(int a, int b){ return a > b ? a : b; }

inline LL Min(LL a, LL b){ return a < b ? a : b; }

inline LL Max(LL a, LL b){ return a > b ? a : b; }

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

struct node{

    int to, w, next;

};

node a[maxn<<1];

int cnt;

int head[maxn];

bool vis[maxn];

int d[maxn];

int q[maxn];

void add(int u, int v, int w){

    a[cnt].to = v;

    a[cnt].w = w;

    a[cnt].next = head[u];

    head[u] = cnt++;

}

int spfa(int s, int t){

    memset(vis, false, sizeof vis);

    fill(d, d+n+1, INF);

    int front = 0, rear = 0;

    q[rear++] = s;

    d[s] = 0;

    while(front < rear){

        int u = q[front++];

        vis[u] = false;

        for(int i = head[u]; ~i; i = a[i].next){

            int v = a[i].to;

            if(d[v] > d[u] + a[i].w){

                d[v] = d[u] + a[i].w;

                if(!vis[v]) q[rear++] = v, vis[v] = true;

            }

        }

    }

    return d[t];

}

int main(){

    int T;  cin >> T;

    while(T--){

        scanf("%d %d", &n, &m);

        int u, v, w;

        cnt = 0;

        memset(head, -1, sizeof head);

        for(int i = 1; i < n; ++i){

            scanf("%d %d %d", &u, &v, &w);

            add(u, v, w);

            add(v, u, w);

        }

        while(m--){

            scanf("%d %d", &u, &v);

            printf("%d\n", spfa(u, v));

        }

    }

    return 0;

}
上一篇：photoshop设计制作出圆形黑色开关按钮


下一篇：mybatis映射文件mapper.xml的写法(collections...)