fork(1) download 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <vector>
  5. #include <stack>
  6. #include <queue>
  7. #include <set>
  8. #include <map>
  9. #include <algorithm>
  10. #include <string>
  11. #include <cstring>
  12. #define MID(x,y) ((x+y)/2)
  13. #define mem(a,b) memset(a,b,sizeof(a))
  14. using namespace std;
  15. const int MAXV = 50005;
  16. const int MAXE = 100005;
  17. struct Gragh{
  18.     struct Gragh_Node{
  19.         int u, v, w;
  20.         int opp;
  21.         int next;
  22.         int res;        //存Query的结果
  23.     }arc[MAXE];
  24.     int cnt, head[MAXV];
  25.     void init(){
  26.         cnt = 0;
  27.         memset(head, -1, sizeof(head));
  28.     }
  29.     void g_insert(int u, int v, int w){
  30.         arc[cnt].u = u;
  31.         arc[cnt].v = v;
  32.         arc[cnt].w = w;
  33.         arc[cnt].res = 0;
  34.         arc[cnt].next = head[u];
  35.         head[u] = cnt ++;
  36.  
  37.         arc[cnt].u = v;
  38.         arc[cnt].v = u;
  39.         arc[cnt].w = w;
  40.         arc[cnt].res = 0;
  41.         arc[cnt].next = head[v];
  42.         head[v] = cnt ++;
  43.     }
  44.     void q_insert(int u, int v){
  45.         arc[cnt].u = u;
  46.         arc[cnt].v = v;
  47.         arc[cnt].res = 0;
  48.         arc[cnt].next = head[u];
  49.         arc[cnt].opp = cnt + 1;
  50.         head[u] = cnt ++;
  51.         arc[cnt].u = v;
  52.         arc[cnt].v = u;
  53.         arc[cnt].res = 0;
  54.         arc[cnt].next = head[v];
  55.         arc[cnt].opp = cnt - 1;
  56.         head[v] = cnt ++;
  57.     }
  58. };
  59. struct Disjoint_Sets{
  60.     //略
  61. };
  62. struct LCA{
  63.     Gragh G, Q;         //G存图(树); Q存查询,可以把每个询问当成一个无向边存储
  64.     Disjoint_Sets DS;
  65.     int ancestor[MAXV];
  66.     int indegree[MAXV];
  67.     int dist[MAXV];
  68.     bool vis[MAXV];
  69.     bool flag[MAXV];
  70.     void init(int n){
  71.         memset(ancestor, 0, sizeof(ancestor));
  72.         memset(vis, 0, sizeof(vis));
  73.         memset(flag, 0, sizeof(flag));
  74.         memset(dist, 0, sizeof(dist));
  75.         G.init();
  76.         Q.init();
  77.         DS.Init(n);
  78.     }
  79.     void insert_gragh(int u, int v, int w){
  80.         G.g_insert(u, v, w);
  81.     }
  82.     void insert_query(int u, int v){
  83.         Q.q_insert(u, v);
  84.     }
  85.     void lca(int u, int dis){
  86.         ancestor[u] = u;
  87.         dist[u] = dis;
  88.         flag[u] = 1;
  89.         for (int i = G.head[u]; i != -1; i = G.arc[i].next){
  90.             int v = G.arc[i].v;
  91.             if (!flag[v]){
  92.                 lca(v, dis+G.arc[i].w);
  93.                 DS.Union(u, v);
  94.                 ancestor[DS.Father(u)] = u;
  95.             }
  96.         }
  97.         vis[u] = 1;
  98.         for (int i = Q.head[u]; i != -1; i = Q.arc[i].next){
  99.             int v = Q.arc[i].v;
  100.             if (vis[v]){
  101.                 Q.arc[i].res = dist[u] + dist[v] - 2*dist[ancestor[DS.Father(v)]];
  102.                 Q.arc[Q.arc[i].opp].res = dist[u] + dist[v] - 2*dist[ancestor[DS.Father(v)]];
  103.             }
  104.         }
  105.     }
  106.     void solve(int n){
  107. //        memset(indegree, 0, sizeof(indegree));
  108. //        for (int i = 0; i < G.cnt; i ++){
  109. //            indegree[G.arc[i].v] ++;
  110. //        }
  111. //        for (int i = 1; i <= n; i ++){
  112. //            if (indegree[i] == 0)
  113. //                lca(i, 0);
  114. //        }
  115.         lca(1, 0);
  116.     }
  117. }L;
  118. int main(){
  119.     int n, m;
  120.     scanf("%d %d", &n, &m);
  121.     L.init(n);
  122.     for (int i = 0; i < m; i ++){
  123.         int u, v, w;
  124.         scanf("%d %d %d %*c", &u, &v, &w);
  125.         L.insert_gragh(u, v, w);
  126.     }
  127.     int q;
  128.     scanf("%d", &q);
  129.     for (int i = 0; i < q; i ++){
  130.         int u, v;
  131.         scanf("%d %d", &u, &v);
  132.         L.insert_query(u, v);
  133.     }
  134.     L.solve(n);
  135.     for (int i = 1; i <= q; i ++){
  136.         printf("%d\n", L.Q.arc[2*i-1].res);
  137.     }
  138. 	return 0;
  139. }
  140.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/A0M7Ms
LCA --- POJ 1986 求树上两点之间的距离。稍微多了一个距离，但是本质还是一样的对于一个询问d[u,v]=dis[u]+dis[v]-dis[LCA(u,v)]可以一边LCA一边动态修改当前点到根的距离
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!