CodeForces1051F LCA + Floyd

时间：2023-03-10 01:47:25
CodeForces1051F LCA + Floyd

题意：给定一个10W的无向联通图，和10W的询问，每个询问求任意两点间的距离，限制条件是边数-点数不超过20

一般来说图上任意两点间的距离都会采用Floyd算法直接做，但是这个数据范围显然是不合理的，好在给了我们一个限制条件。

我们先考虑，如果边数是点数N - 1，这就变成了一颗N结点的树，两点间的距离可以用ln的时间复杂度用LCA的算法求出，在本题中加上了20条额外的边，事实上我们单独考虑每个边对于最短路的贡献，也就是原本走lca路线的边走这些边是不是会快一些，

有了这个想法，我们可以将树上的路径看作大路，也就是正常走的路径，加上的额外的边看作通道，对于每一次询问，只要考虑走通道是否能实现更优的路径即可。

所以整体的思路就变成了LCA求正常路径（中途顺手求了一个重心作为根节点），然后floyd预处理通道之间的关系，询问的时候就是40 * 40 * Q的时间复杂度输出。

#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <string>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <functional>

using namespace std;

#define For(i, x, y) for(int i=x;i<=y;i++)

#define _For(i, x, y) for(int i=x;i>=y;i--)

#define Mem(f, x) memset(f,x,sizeof(f))

#define Sca(x) scanf("%d", &x)

#define Sca2(x,y) scanf("%d%d",&x,&y)

#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define Scl(x) scanf("%lld",&x);

#define Pri(x) printf("%d\n", x)

#define Prl(x) printf("%lld\n",x);

#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();

#define LL long long

#define ULL unsigned long long

#define mp make_pair

#define PII pair<int,int>

#define PIL pair<int,long long>

#define PLL pair<long long,long long>

#define pb push_back

#define fi first

#define se second

inline LL read(){LL now=;register char c=getchar();for(;!isdigit(c);c=getchar());

for(;isdigit(c);now=now*+c-'',c=getchar());return now;}

typedef vector<int> VI;

const double eps = 1e-;

const int maxn = 1e5 + ;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

int N,M,K;

int fa[maxn];

struct Edge{

    int to,next;

    LL dis;

}edge[maxn * ];

struct Edge2{

    int u,v;

    LL w;

    Edge2(int u = ,int v =  ,LL w = ):u(u),v(v),w(w) {}

}E[maxn];

int head[maxn],tot;

void init(){

    for(int i = ; i <= N ; i ++){

         fa[i] = i;

         head[i] = -;

    }

    tot = ;

}

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

    edge[tot].to = v;

    edge[tot].dis = w;

    edge[tot].next = head[u];

    head[u] = tot++;

}

int find(int p){

    return p == fa[p]?p:fa[p] = find(fa[p]);

}

void Union(int a,int b){

    a = find(a); b = find(b);

    fa[a] = b;

}

int v[maxn],size[maxn],root,ans;

void dfsroot(int x){

    v[x] = ,size[x] = ;

    int max_part = ;

    for(int i = head[x] ; ~i ; i = edge[i].next){

        int y = edge[i].to;

        if(v[y]) continue;

        dfsroot(y);

        size[x] += size[y];

        max_part = max(max_part,size[y]);

    }

    max_part = max(max_part,N - size[x]);

    if(max_part < ans){

        ans = max_part;

        root = x;

    }

}

const int SP = ;

int pa[maxn][SP],dep[maxn];

LL dis[maxn];

void dfs(int u,int fa){

    pa[u][] = fa; dep[u] = dep[fa] + ;

    for(int i = ; i < SP ; i ++) pa[u][i] = pa[pa[u][i - ]][i - ];

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

        int v = edge[i].to;

        if(v == fa) continue;

        dis[v] = dis[u] + edge[i].dis;

        dfs(v,u);

    }

}

int lca(int u,int v){

    if(dep[u] < dep[v]) swap(u,v);

    int t = dep[u] - dep[v];

    for(int i =  ; i < SP; i ++) if(t & ( << i)) u = pa[u][i];

    for(int i = SP - ; i >=  ; i --){

        int uu = pa[u][i],vv = pa[v][i];

        if(uu != vv){

            u = uu; v = vv;

        }

    }

    return u == v?u:pa[u][];

}

LL DIS(int u,int v){return dis[u] + dis[v] -  * dis[lca(u,v)];}

LL D[maxn];

int vis[maxn];

int flag[maxn];

LL MAP[][];

LL INIT[maxn][];

int main()

{

    Sca2(N,M); init();

    int cnt = ,num = ;

    for(int i = ; i <= M ; i ++){

        int u = read(); int v = read(); LL w = read();

        if(find(u) == find(v)){

            E[++cnt] = Edge2(u,v,w);

            if(!vis[u]){flag[++num] = u;vis[u] = num;}

            if(!vis[v]){flag[++num] = v;vis[v] = num;}

        }else{

            add(u,v,w); add(v,u,w);

            Union(u,v);

        }

    }

    root = ;ans = INF;

    dfsroot();

    dis[root] = ; dfs(root,-);

    for(int i = ; i <= num ; i ++)

        for(int j = ; j <= num ; j ++)

            MAP[i][j] = DIS(flag[i],flag[j]);

    for(int i = ; i <= cnt;i ++) MAP[vis[E[i].v]][vis[E[i].u]] = MAP[vis[E[i].u]][vis[E[i].v]] = min(MAP[vis[E[i].u]][vis[E[i].v]],E[i].w);

    for(int k = ; k <= num ; k ++)

        for(int i = ; i <= num ; i ++)

            for(int j = ; j <= num ; j ++)

                MAP[i][j] = min(MAP[i][j],MAP[i][k] + MAP[k][j]);

    for(int i = ; i <= N ; i ++)

        for(int j = ; j <= num; j ++)

            INIT[i][j] = DIS(i,flag[j]);

    int q = read();

    while(q--){

        int u= read();int v = read();

        LL ANS = DIS(u,v);

        for(int i = ; i <= num; i ++){

            for(int j = ; j <= num ; j ++){

                ANS = min(ANS,INIT[u][i] + MAP[i][j] + INIT[v][j]);

            }

        }

        Prl(ANS);

    }

    #ifdef VSCode

    system("pause");

    #endif

    return ;

}

相关文章