洛谷 P1967 【货车运输】

题库：洛谷
题号：1967
题目：货车运输
link ：https://www.luogu.com.cn/problem/P1967

Updata 1.22：附上树链剖分的代码，https://paste.ubuntu.com/p/JyQvXW9yxP/

前置知识：

$kruskal$ ：https://www.cnblogs.com/qqq1112/p/11574876.html
$lca$ ：https://www.cnblogs.com/qqq1112/p/11448165.html

思路：

$step1$：

观察题目，发现司机们并不管送货路程的远近，只管能装货物的总数。如果有一条比较远的路，但能装货物的总量更大，司机还是会绕道走的。由此来看，一些较小的边是不会被走到的（除了没有其他路可走），于是我们只需要在保证在没有破坏图的连通性的条件下（但题目没说图一开始就是连通的）删掉较小的边。完成以上操作，我们只需先建立一个最大生成树即可（注意先把图的数据存起来，然后边跑 $kruskal$ 边将确定的边再连上），其实也是方便完成 $step2$ 的操作罢了。

操作方式：处理最大生成树的方法和处理最小生成树的方法等同（千万不要把 $cmp$ 里的大于号小于号给写反了），只不过要在 $kruskal$ 中把已经确定的边连上，$warning$ —— 是双向边。

$step2$：

处理完了图的操作后，我们思考如何将司机所能运输的最大载货量给求出来，同时，看数据，加上外层的一层循环，只能用 $log(n)$ 的复杂度求出路径上的距离， $lca$ 恰恰是如此。在处理点深度和父节点时，可以像 $fa[u][i]$ 一样建立一个 $q[u][i]$ ，表示从$u$到$u$的第 $2$ⁱ个祖先上的路径的最小边权是多少（但这里边权存在深度较深的那个节点上面了）。然后边跑 $lca$ 在起点和终点向上“跳”时进行更新 $ans$，及 $ans$ $=$ $min(ans$, $min(q[x][i]$, $q[y][i]))$，还有在 $x$，$y$中较深的节点向上“跳”时，也需要更新 $ans$，及 $ans$ $=$ $min(ans$, $q[u][i])$。当然，在初始化深度和 $fa$ 数组的时候，也需要处理一下 $q$ 数组的初始化，及 $q[u][i]$ $=$ $min(q[u][i$ $-$ $1]$, $q[fa[u][i$ $-$ $1]][i$ $-$ $1])$。然后，就只需要边跑 $lca$ 边更新答案就好了。

操作方式：正常 $lca$ $+$ 更新 $q$ 数组与 $ans$。

$code$：

  1 #include <bits/stdc++.h>
  2 #define INF 0x3f3f3f3f
  3 using namespace std;
  4 int n, m, p, head[1000001], num, depth[1000001], fa[1000001][21], q[1000001][21], Fa[1000001], size[1000001];//size数组是按秩合并里需要的，可以不管 
  5 struct Node
  6 {
  7     int next, to, val;
  8 }stu[2000001];
  9 struct node
 10 {
 11     int x, y, z;
 12 }tree[2000001];//kruskal里需要用到的数组 
 13 inline int cmp(node a, node b)
 14 {
 15     return a.z > b.z;
 16 }
 17 inline void add(int x, int y, int z)//加边 
 18 {
 19     stu[++num].next = head[x];
 20     stu[num].to = y;
 21     stu[num].val = z;
 22     head[x] = num;
 23     return;
 24 }
 25 inline int find(int x)//查找 
 26 {
 27     return Fa[x] == x ? Fa[x] : Fa[x] = find(Fa[x]);
 28 }
 29 inline void unity(int x, int y)//按秩合并 
 30 {
 31     int r1 = find(x);
 32     int r2 = find(y);
 33     if(size[r1] > size[r2])
 34     {
 35         Fa[r2] = r1;
 36         size[r1] += size[r2];
 37     }
 38     else
 39     {
 40         Fa[r1] = r2;
 41         size[r2] += size[r1];
 42     }
 43     return;
 44 }
 45 inline void kruskal()//最大生成树 
 46 {
 47     int k = 0; 
 48     sort(tree + 1, tree + m + 1, cmp);
 49     for(register int i = 1; i <= m; ++i)
 50     {
 51         if(find(tree[i].x) != find(tree[i].y))
 52         {
 53             unity(tree[i].x, tree[i].y);
 54             add(tree[i].x, tree[i].y, tree[i].z);
 55             add(tree[i].y, tree[i].x, tree[i].z);
 56             ++k;
 57             if(k == n - 1)
 58             {
 59                 return;
 60             }
 61         }
 62     }
 63     return;
 64 }
 65 inline void dfs(int u, int father, int value)//value是边权，存在深度深的节点上面 
 66 {
 67     fa[u][0] = father;
 68     q[u][0] = value;
 69     depth[u] = depth[father] + 1;
 70     int maxn = ceil(log(depth[u]) / log(2));
 71     for(register int i = 1; i <= maxn; ++i)
 72     {
 73         fa[u][i] = fa[fa[u][i - 1]][i - 1];
 74         q[u][i] = min(q[u][i - 1], q[fa[u][i - 1]][i - 1]);
 75     }
 76     for(register int i = head[u]; i; i = stu[i].next)
 77     {
 78         int k = stu[i].to;
 79         if(k != father)
 80         {
 81             dfs(k, u, stu[i].val);
 82         }
 83     }
 84     return;
 85 }
 86 inline void up(int &u, int step, int &ans)//将深度跳到相同位置 
 87 {
 88     int maxn = ceil(log(depth[u]) / log(2));
 89     for(register int i = 0; i <= maxn; ++i)
 90     {
 91         if(step & (1 << i))
 92         {
 93             ans = min(ans, q[u][i]);
 94             u = fa[u][i];
 95         }
 96     }
 97     return;
 98 }
 99 inline int lca(int x, int y)//lca 
100 {
101     if(find(x) != find(y))//不相连 
102     {
103         return -1;
104     }
105     int ans = INF;
106     if(depth[x] < depth[y])
107     {
108         swap(x, y);
109     }
110     up(x, depth[x] - depth[y], ans);
111     if(x == y)
112     {
113         return ans;
114     }
115     int maxn = ceil(log(depth[x]) / log(2));
116     for(register int i = maxn; i >= 0; --i)
117     {
118         if(fa[x][i] != fa[y][i])
119         {
120             ans = min(ans, min(q[x][i], q[y][i]));
121             x = fa[x][i];
122             y = fa[y][i];
123         }
124     }
125     return min(ans, min(q[x][0], q[y][0]));//最后父节点别忘了 
126 }
127 signed main()
128 {
129     scanf("%d %d", &n, &m);
130     for(register int i = 1; i <= n; ++i)
131     {
132         Fa[i] = i;
133         size[i] = 1;
134     }
135     for(register int i = 1, x, y, z; i <= m; ++i)
136     {
137         scanf("%d %d %d", &tree[i].x, &tree[i].y, &tree[i].z);
138     }
139     kruskal();
140     for(register int i = 1; i <= n; ++i)//注意该图可能不连通，于是需要多次dfs初始化 
141     {
142         if(!depth[i])
143         {
144             dfs(i, 0, INF);
145         }
146     }
147     scanf("%d", &p);
148     for(register int i = 1, x, y; i <= p; ++i)
149     {
150         scanf("%d %d", &x, &y);
151         printf("%d\n", lca(x, y));
152     }
153     return 0;
154 }

洛谷 P1967 【货车运输】

推荐阅读