首页 > 其他分享 >[Violet 6]故乡的梦 题解

[Violet 6]故乡的梦 题解

时间:2024-08-05 21:05:46浏览次数:11  
标签:idx int 题解 故乡 tree 200010 long Violet dis

前言

题目链接:Hydro & bzoj

题意简述

无向联通图给出起点终点,多次询问删边后最短路,或报告不连通。

\(n, m, q \leq 2 \times 10^5\)。

题目分析

首先想到,如果删掉的边不是原来最短路的边,那么最短路不会发生变化。因此我们只需考虑删除了原来在最短路上的边。

不妨把原先最短路任选一条拉下来,记作 \(d_1 \ldots d_k\),其中 \(d_1 = s, s_k = t\)。设删除的边 \((u, v) = (d_{p}, d_{p+1})\)。

我们为了走到 \(t\),不得不经过一些更长的边。考虑以 \(s\) 为根,建出最短路径树。只进过树边到达不了 \(t\),所以要进过一些非树边,并且只经过一条非树边,因为经过更多的非树边是不优的。记这条非树边是 \(x \rightarrow y\),那么我们要找到 \(y \rightarrow t\) 的最短路径,这个以 \(t\) 为起点跑一边最短路即可。

所以,问题转化为,找到新的最短路 \(s \rightarrow d_{i} \rightarrow x \rightarrow y \rightarrow d_{j} \rightarrow t\),其中 \(i \leq p\) 并且 \(j \geq p + 1\)。那么 \(d_i\) 就是以 \(s\) 为根的最短路径树上,\(x\) 到链 \(s \sim t\) 的结点,\(d_j\) 是以 \(t\) 为根的最短路径树上, \(y\) 到链 \(s \sim t\) 的结点。

用 BFS 或 DFS 什么的标记一下预处理很方便。不妨把 \((x, y)\) 这条非树边挂在 \(d_i\) 上,记作二元组 \(v_i = (d_j, len)\),其中 \(len\) 是经过 \((x, y)\) 最短路长度。查询变成了在 \(v_{1 \sim p}\) 中,前者 \(\geq p + 1\) 的后者的最小值。

可以用堆,不断加入、删除,统计答案。

可以用线段树,把 \(i \sim j - 1\) 覆盖最小值。

可以用主席树,变成查询 \(p\) 版本 \(\geq p + 1\) 的最小值。

代码

使用了主席树,并略去了快读快写。

// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast", "inline", "-ffast-math")
// #pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int n, m, S, T, Q;

struct Graph{
	struct node{
		int to, len, nxt;
	} edge[200010 << 1];
	int eid = 1, head[200010];
	inline void add(int u, int v, int w = 0){
		edge[++eid] = {v, w, head[u]};
		head[u] = eid;
	}
	inline node & operator [] (const int x){
		return edge[x];
	}
} xym;

template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;

int line[200010], whr[200010], tim;
bool inpath[200010];

struct Rebuild_Tree {
	long long dis[200010];
	int fr[200010], dpt[200010], bl[200010];
	Graph yzh;
	void dfs(int now, int anc) {
		bl[now] = anc;
		for (int i = yzh.head[now], to; to = yzh[i].to, i; i = yzh[i].nxt) {
			dpt[to] = dpt[now] + 1;
			dfs(to, inpath[to] ? to : anc);
		}
	}
	void build(int S) {
		minHeap<pair<long long, int>> Q;
		memset(dis, 0x3f, sizeof (long long) * (n + 1));
		Q.push({dis[S] = 0, S});
		while (!Q.empty()) {
			auto [ndis, now] = Q.top(); Q.pop();
			if (ndis > dis[now]) continue;
			for (int i = xym.head[now], to, len; to = xym[i].to, len = xym[i].len, i; i = xym[i].nxt) {
				if (dis[to] > dis[now] + len) {
					Q.push({dis[to] = dis[now] + len, to});
					fr[to] = i ^ 1;
				}
			}
		}
		for (int i = 1; i <= n; ++i) if (i != S)
			yzh.add(xym[fr[i]].to, i);
	}
} S_tree, T_tree;

void getpath() {
	for (int now = T; now; now = xym[S_tree.fr[now]].to) ++tim;
	for (int now = T, cnt = 0; now; now = xym[S_tree.fr[now]].to, ++cnt)
		line[tim - cnt] = now, whr[now] = tim - cnt, inpath[now] = true;
}

vector<pair<int, long long>> trans[200010];

struct President_Segment_Tree {
	struct node {
		int lson, rson;
		long long val;
	};
	static node tree[200010 * 100];
	static int tot;
	
	static inline int copyNode(int idx) {
		return tree[++tot] = idx ? tree[idx] : node {0, 0, 0x3f3f3f3f3f3f3f3f}, tot;
	}
	
	int root[200010];
	
	void modify(int &idx, int l, int r, int p, long long v){
		if (r < p || l > p) return;
		idx = copyNode(idx), tree[idx].val = min(tree[idx].val, v);
		if (l == r) return;
		int mid = (l + r) >> 1;
		modify(tree[idx].lson, l, mid, p, v);
		modify(tree[idx].rson, mid + 1, r, p, v);
	}
	
	long long query(int idx, int trl, int trr, int l, int r) {
		if (trl > r || trr < l || !idx) return 0x3f3f3f3f3f3f3f3f;
		if (l <= trl && trr <= r) return tree[idx].val;
		int mid = (trl + trr) >> 1;
		return min(query(tree[idx].lson, trl, mid, l, r), query(tree[idx].rson, mid + 1, trr, l, r));
	}
} tree;

President_Segment_Tree::node President_Segment_Tree::tree[200010 * 100];
int President_Segment_Tree::tot;

signed main() {
	fread(buf, 1, MAX, stdin);
	read(n), read(m);
	for (int i = 1, u, v, w; i <= m; ++i) {
		read(u), read(v), read(w);
		xym.add(u, v, w);
		xym.add(v, u, w);
	}
	read(S), read(T), S_tree.build(S), T_tree.build(T), getpath(), S_tree.dfs(S, S), T_tree.dfs(T, T);
	for (int u = 1; u <= n; ++u) {
		for (int i = xym.head[u], v, len; v = xym[i].to, len = xym[i].len, i; i = xym[i].nxt) {
			if ((i ^ 1 ^ S_tree.fr[v]) && whr[T_tree.bl[v]] > whr[S_tree.bl[u]]) {
				trans[whr[S_tree.bl[u]]].push_back({whr[T_tree.bl[v]], S_tree.dis[u] + len + T_tree.dis[v]});
			}
		}
	}
	for (int i = 1; i <= tim; ++i) {
		tree.root[i] = tree.root[i - 1];
		for (const auto& [to, len]: trans[i]) {
			tree.modify(tree.root[i], 1, tim, to, len);
		}
	}
	read(Q);
	for (int i = 1, u, v; i <= Q; ++i) {
		read(u), read(v);
		if (S_tree.dpt[u] > S_tree.dpt[v]) swap(u, v);
		if (xym[S_tree.fr[v]].to == u && inpath[v]) {
			u = whr[u], v = whr[v];
			long long res = tree.query(tree.root[u], 1, tim, v, tim);
			if (res == 0x3f3f3f3f3f3f3f3f)
				output_inf();
			else
				write(res);
			putchar('\n');
		} else {
			if (S_tree.dis[T] == 0x3f3f3f3f3f3f3f3f)
				output_inf();
			else
				write(S_tree.dis[T]);
			putchar('\n');
		}
	}
	fwrite(obuf, 1, o - obuf, stdout);
	return 0;
}

标签:idx,int,题解,故乡,tree,200010,long,Violet,dis
From: https://www.cnblogs.com/XuYueming/p/18343974

相关文章

  • 洛谷-P9830 题解
    思路分析分析样例:见红线,长宽各为2,存在格点;黄线长2宽3,没有格点。考虑延长黄线使得长4宽6,发现有格点。思考格点,如果长和宽都可以被分成\(p\timesl\)的格式,则存在格点。那么,就能想出:推论1:对于\((0\,\0)\)和\((x\,\y)\)之间没有格点,当且仅当\(\gcd(x\,......
  • P9596 冒泡排序 2 题解
    题目链接。Statement记\(f(A)\)为序列\(A\)的冒泡排序趟数,操作:单点改,全局查\(f(A)\).\(n,m\le5\cdot10^5\),值域1e9.Solution结论:\[Ans=\max_{i\in[1..n]}\left\{\sum_{j\in[1..i]}[A_j>A_i]\right\}\]怎么观察出来啊QAQ证明:对于每个位置\(p\),观察到每趟都......
  • AGC046C 题解
    blog。好菜啊,不会这题,来写个题解/kel。很难直接做,先找一点性质:操作只改变相对顺序,而总数不变。这启示我们记录每个\(0\)前面的极长\(1\)连续段长度。记第\(i(1\lei\leC)\)个\(0\)对应长度为\(a_i\),就存在下面的等价表述:每次操作可以选定\(i,j(1\lei<j\leC)\),......
  • 洛谷-P9574 题解
    思路分析分析样例:==TTBTBTTBTBTTTBTTB->TTBTTBBTTBTTTBTTB->TTBTTBTBBTTTTBTTB->TTBTTBTBBTTTTTBBT----1-----2-----3---4--观察区块2,发现BTTB进行操作后与右边的TB再次构成BTTB,我们发现在这个区块内,可以从左向右不断操作,我们称这种特性为传递性,可......
  • AT_abl_e Replace Digits 题解
    题目传送门前置知识线段树解法需要维护区间信息,考虑使用线段树维护。预处理出\(\overline{xx\dotsx}\),其中\(x\in\{1,2,3,4,5,6,7,8,9\}\),便于区间赋值。然后就是普通的线段树板子了。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#de......
  • AGC027C 题解
    注意到如果可以构造出所有由\(\texttt{A}\)和\(\texttt{B}\)组成的字符串,那么在图上游走的路径必须成环,并且的环上的每一个点都必须同时有一个\(\texttt{A}\)邻居和\(\texttt{B}\)邻居。于是可以考虑把点拆分为入点和出点,相邻两个点为\(\texttt{AA},\texttt{BB}\)的,从......
  • npm下载包时报错 Unexpected token ‘.‘问题解决
    项目场景:项目需要使用node18.12.0以上版本的,但是npm下载显示异常问题描述当通过nvm切换nodejs版本为16以上时,npminstall[package]报错:Unexpectedtoken'.'原因分析:提示:该问题不是npm的问题,也不是nodejs的问题,是nvm-windows的问题我是通过nvm-windows已经更新版本......
  • 《数据结构习题解析与实验指导_李冬梅,张琪编著》总结出的大纲
        下面大纲为《数据结构习题解析与实验指导_李冬梅,张琪编著》总结出的大纲,可装13学习下:          ......
  • Codeforces Round 963 (Div. 2) D题解
    CodeforcesRound963D题目描述给定两个正整数n和k以及另一个由n个整数组成的数组a。在一次操作中,可以选择a中大小为k的任意一个子数组,然后将其从数组中删除,而不改变其他元素的顺序。更正式地说,假设(l,r)是对子数组a[l],a[l+1],...,a[r]的操作,使得r-l+1......
  • leetcode200. 岛屿数量C++题解,精美图例和流程图,一题带你弄懂图的dfs遍历算法
    leetcode200.岛屿数量给你一个由‘1’(陆地)和‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。示例1:输入:grid=[[“1”,“1”,“1”,......