CodeForces1051F LCA + Floyd-白红宇

CodeForces1051F LCA + Floyd

阅读量：5079 次

发布时间：2019-06-12

本文共 4171 字，大约阅读时间需要 13 分钟。

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

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

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

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

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

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    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
                    
                     #define PIL pair
                     
                      #define PLL pair
                      
                       #define pb push_back#define fi first#define se second inline LL read(){LL now=0;register char c=getchar();for(;!isdigit(c);c=getchar());for(;isdigit(c);now=now*10+c-'0',c=getchar());return now;}typedef vector
                       
                         VI;const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int fa[maxn];struct Edge{ int to,next; LL dis;}edge[maxn * 2];struct Edge2{ int u,v; LL w; Edge2(int u = 0,int v = 0 ,LL w = 0):u(u),v(v),w(w) {}}E[maxn];int head[maxn],tot;void init(){ for(int i = 1; i <= N ; i ++){ fa[i] = i; head[i] = -1; } tot = 0;}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] = 1,size[x] = 1; int max_part = 0; 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 = 20;int pa[maxn][SP],dep[maxn];LL dis[maxn];void dfs(int u,int fa){ pa[u][0] = fa; dep[u] = dep[fa] + 1; for(int i = 1; i < SP ; i ++) pa[u][i] = pa[pa[u][i - 1]][i - 1]; 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 = 0 ; i < SP; i ++) if(t & (1 << i)) u = pa[u][i]; for(int i = SP - 1; i >= 0 ; i --){ int uu = pa[u][i],vv = pa[v][i]; if(uu != vv){ u = uu; v = vv; } } return u == v?u:pa[u][0];}LL DIS(int u,int v){ return dis[u] + dis[v] - 2 * dis[lca(u,v)];}LL D[maxn];int vis[maxn];int flag[maxn];LL MAP[50][50];LL INIT[maxn][50];int main(){ Sca2(N,M); init(); int cnt = 0,num = 0; for(int i = 1; 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 = 1;ans = INF; dfsroot(1); dis[root] = 0; dfs(root,-1); for(int i = 1; i <= num ; i ++) for(int j = 1; j <= num ; j ++) MAP[i][j] = DIS(flag[i],flag[j]); for(int i = 1; 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 = 1; k <= num ; k ++) for(int i = 1; i <= num ; i ++) for(int j = 1; j <= num ; j ++) MAP[i][j] = min(MAP[i][j],MAP[i][k] + MAP[k][j]); for(int i = 1; i <= N ; i ++) for(int j = 1; 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 = 1; i <= num; i ++){ for(int j = 1; j <= num ; j ++){ ANS = min(ANS,INIT[u][i] + MAP[i][j] + INIT[v][j]); } } Prl(ANS); } #ifdef VSCode system("pause"); #endif return 0;}

转载于:https://www.cnblogs.com/Hugh-Locke/p/9965676.html

你可能感兴趣的文章