网站主办者是什么意思,医院网站需要前置审批,鲜花网站建设项目策划书,怎么自己创建小程序题面在这里就不放了。 同步赛在做这个题的时候#xff0c;心里有点纠结#xff0c;很容易想到离线的做法#xff0c;将边和询问一起按水位线排序#xff0c;模拟水位下降#xff0c;维护当前的各个联通块中距离$1$最近的距离#xff0c;每次遇到询问时输出所在联通块的信…题面在这里就不放了。 同步赛在做这个题的时候心里有点纠结很容易想到离线的做法将边和询问一起按水位线排序模拟水位下降维护当前的各个联通块中距离$1$最近的距离每次遇到询问时输出所在联通块的信息。 离线的思路对满分做法有一定的启发性很容易想到将并查集持久化一下就能支持在线了。 但是这个是两个$log$的有卡常的风险也不是很方便写。 当时思考了一下就快速写完离线做法就去做其他题了。 对于这道题有一个更好的做法Kruskal重构树。 事实上如果你了解这个东西那你就能很快的给出解那仅此以这道题作为学习Kruskal重构树的例子。 先给出一个经典的模型 给定一张无向图每次询问两点之间所有简单路径中最大边权的最小值。一个常规的做法就是建出最小生成树答案就是树上路径的最大边权正确性显然。 当然也可以用我们要讲的Kruskal重构树来解决算法虽不同思想类似。 Kruskal中我们连接两个联通块子树时直接用一条边将对应的两个点相连但在Kruskal重构树中我们先建一个虚点作为两个子树的树上父亲让两个联通块分别与该点相连注意的是要维护并查集合并时的有序性。 我们称新建的虚点为方点代表了原图中的一条边原图中的点为圆点则该树有一些优雅的性质 这是一颗二叉树并且相当于一个堆因为边是有顺序合并的。最小生成树上路径的边权信息转化成了点权信息。那么回顾刚刚的那个模型每个询问就相当于回答Kruskal重构树上两点$lca$的权值。 最后在回来看这道题就显得十分轻松了。 我们把每条边按照水位线从高到低依次插入可以发现每次规定一个水位下限车子能走的范围对应了Kruskal重构树上的一棵子树那么每次只要倍增找到最紧的那个限制的点就可以了。 1 #include cstdio2 #include queue3 #include cstring4 #include algorithm5 6 typedef long long LL;7 const int N 600005, INF 2e9 7, LOG 21;8 9 int tc, n, m, Qi, k, s;10 int dis[N], flg[N], val[N], mdi[N], gr[LOG][N];11 std::priority_queuestd::pairint, int Q;12 13 inline void Read(int x) {14 x 0; static char c;15 for (c getchar(); c 0 || c 9; c getchar());16 for (; c 0 c 9; x (x 3) (x 1) c - 0, c getchar());17 }18 19 struct Edge {20 int u, v, a;21 inline friend bool operator (Edge a, Edge b) {22 return a.a b.a;23 }24 } e[N];25 26 int yun, las[N], to[N 1], pre[N 1], wi[N 1];27 inline void Add(int a, int b, int c 0) {28 to[yun] b; wi[yun] c; pre[yun] las[a]; las[a] yun;29 }30 void Gragh_clear() {31 memset(gr, 0, sizeof gr);32 memset(las, 0, sizeof las);33 yun 0;34 }35 36 namespace DSU {37 int fa[N];38 void Init() {39 for (int i 1; i n m; i) {40 fa[i] i;41 if (i n) mdi[i] dis[i], val[i] -1;42 }43 }44 int Seek(int x) {45 return (x fa[x])? (x) : (fa[x] Seek(fa[x]));46 }47 void Merge(int x, int y) {48 fa[Seek(y)] x;49 }50 }51 52 void Dij() {53 for (int i 1; i n; i) {54 dis[i] INF; flg[i] 0;55 }56 dis[1] 0;57 Q.push(std::make_pair(0, 1));58 for (; !Q.empty(); ) {59 int x Q.top().second; Q.pop();60 if (flg[x]) continue;61 flg[x] 1;62 for (int i las[x]; i; i pre[i]) {63 if (dis[to[i]] dis[x] wi[i]) {64 dis[to[i]] dis[x] wi[i];65 Q.push(std::make_pair(-dis[to[i]], to[i]));66 }67 }68 }69 }70 71 int main() {72 freopen(return.in, r, stdin);73 freopen(return.out, w, stdout);74 75 scanf(%d, tc);76 for (; tc; --tc) {77 scanf(%d%d, n, m);78 Gragh_clear();79 for (int i 1, x, y, a, l; i m; i) {80 //scanf(%d%d%d%d, x, y, l, a);81 Read(x); Read(y); Read(l); Read(a);82 Add(x, y, l); Add(y, x, l);83 e[i] (Edge) { x, y, a };84 }85 Dij(); DSU::Init();86 87 std::sort(e 1, e 1 m);88 for (int i 1; i m; i) {89 int x DSU::Seek(e[i].u), y DSU::Seek(e[i].v);90 if (x y) continue;91 val[i n] e[i].a;92 mdi[i n] std::min(mdi[x], mdi[y]);93 DSU::Merge(i n, x); DSU::Merge(i n, y);94 gr[0][x] gr[0][y] i n;95 }96 97 for (int i 1; i LOG; i) {98 for (int j 1; j n m; j) {99 if (gr[i - 1][j]) gr[i][j] gr[i - 1][gr[i - 1][j]];
100 }
101 }
102
103 scanf(%d%d%d, Qi, k, s);
104 for (int x, a, lans 0; Qi; --Qi) {
105 //scanf(%d%d, x, a);
106 Read(x); Read(a);
107 x (x (LL) k * lans - 1) % n 1;
108 a (a (LL) k * lans) % (s 1);
109 for (int i LOG - 1; ~i; --i) {
110 if (gr[i][x] val[gr[i][x]] a) x gr[i][x];
111 }
112 printf(%d\n, mdi[x]);
113 lans mdi[x];
114 }
115 }
116
117 return 0;
118 } View Code $\bigodot$技巧套路 kruskal重构树的构建最小生成树上最值问题的再探。转载于:https://www.cnblogs.com/Dance-Of-Faith/p/9333015.html
