ZOJ Problem Set - 3195 Design the city 【Tarjan离线LCA】

迈不过友情╰ 2022-08-13 16:38 171阅读 0赞

题目：[ZOJ Problem Set - 3195 Design the city][]

题意：给出一个图，求三点的连起来的距离。

分析：分别求出三点中任意两点的距离 / 2 = ans

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    #define N 50010
    #define M 20010
    
    struct Node
    {
        int to,val;
    };
    vector<Node> g[N];
    struct ask{
        int u,v,lca;
    };
    vector<ask> e;
    vector<int> query[N];
    int fa[N],ance[N],dir[N];
    bool vis[N];
    
    inline void add_Node(int u ,int v,int w)
    {
        g[u].push_back((Node){v,w});
        g[v].push_back((Node){u,w});
    }
    
    inline void add_ask(int u ,int v )
    {
        e.push_back((ask){u,v,-1});
        e.push_back((ask){v,u,-1});
        int len = e.size()-1;
        query[v].push_back(len);
        query[u].push_back(len-1);
    }
    
    int find(int x){
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    
    void Tarjan(int u,int val)
    {
        vis[u] = true;
        ance[u] = fa[u] = u;
        dir[u] = val;
        for(int i=0;i<g[u].size();i++)
        {
            Node tmp = g[u][i];
            if(!vis[tmp.to])
            {
                Tarjan(tmp.to,val+tmp.val);
                fa[tmp.to] = u;
            }
        }
        for(int i=0;i<query[u].size();i++)
        {
            int num = query[u][i];
            ask& tmp = e[num];
            if(vis[tmp.v])
            {
                tmp.lca = e[num^1].lca = ance[find(tmp.v)];
            }
        }
    }
    void Clear(int n)
    {
        memset(vis,false,sizeof(vis));
        for(int i=0;i<=n;i++){
            g[i].clear();
            query[i].clear();
        }
        e.clear();
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,m,fack = 0;
        while(~scanf("%d",&n))
        {
            Clear(n);
            for(int i=1;i<n;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                add_Node(x,y,z);
            }
            scanf("%d",&m);
            for(int i=0;i<m;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                add_ask(x,y);
                add_ask(x,z);
                add_ask(y,z);
            }
            Tarjan(0,0);
            int ans = 0;
            if(fack)
                puts("");
            fack = 1;
            for(int i=0;i<3*m;i++)
            {
                ans+=( dir[e[i*2].u] + dir[e[i*2].v] - 2*dir[e[i*2].lca] );
                if(i%3==2){
                    printf("%d\n",ans/2);
                    ans = 0;
                }
            }
        }
        return 0;
    }

[ZOJ Problem Set - 3195 Design the city]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3320