CF938G Shortest Path Queries

Solution

套路題。

$xor$最短路可以用線性基維護（把每個環的邊權異或和放進線性基，詢問時把樹邊路徑邊權異或和放在線性基里跑出最小值即可）。

然后因為線性基刪除比較慢而麻煩（注意線性基是有辦法動態加刪元素的），因此動態加刪邊可以用線段樹分治+可撤銷帶權并查集實現。

時間復雜度$O(nl{g}^{2}n)$。

Code（最近順便改了改碼風）

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI;const lod eps = 1e-11; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 62; const int mods = 998244353; const int MAXN = 1000005; const int INF = 0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f = 1, x = 0; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }return x * f; } map<PR, PR> Map; int n, m, base[30], btop = 0, bstk[MAXN], f[MAXN], num[MAXN], d[MAXN], Ans[MAXN], utop = 0; struct ustknode{ int u, v, c; } ustk[MAXN]; struct Cnode{ int x, y, c; }; struct Qnode{ int id, x, y; }; vector<Cnode> C[MAXN]; vector<Qnode> Q[MAXN]; void insert(int x) {for (int i = 29; i >= 0; -- i)if ((x >> i) & 1) {if (!base[i]) { base[i] = x, bstk[++btop] = i; return; }x ^= base[i];} } int getmn(int x) {for (int i = 29; i >= 0; -- i) upmin(x, x ^ base[i]);return x; } int find(int x) { return f[x] == x ? f[x] : find(f[x]); } int getdis(int x) { return f[x] == x ? d[x] : getdis(f[x]) ^ d[x]; } void unions(int u, int v, int c) {if (num[u] < num[v]) swap(u, v);ustk[++utop] = (ustknode){u, v, c}, f[v] = u, d[v] ^= c, num[u] += num[v]; } void update(int x, int l, int r, int L, int R, Cnode y) {if (l >= L && r <= R) { C[x].PB(y); return; }int mid = (l + r) >> 1;if (R <= mid) update(x << 1, l, mid, L, R, y);else if (L > mid) update(x << 1 | 1, mid + 1, r, L, R, y);else update(x << 1, l, mid, L, mid, y), update(x << 1 | 1, mid + 1, r, mid + 1, R, y); } void solve(int x, int l, int r) {int blst = btop, ulst = utop;for (auto t:C[x]) {int u = t.x, v = t.y, c = t.c, uu = find(u), vv = find(v);if (uu == vv) insert(getdis(u) ^ getdis(v) ^ c);else unions(uu, vv, getdis(u) ^ getdis(v) ^ c); }if (l == r) {for (auto t:Q[l]) Ans[t.id] = getmn(getdis(t.x) ^ getdis(t.y));}else {int mid = (l + r) >> 1;solve(x << 1, l, mid);solve(x << 1 | 1, mid + 1, r);}while (btop > blst) base[bstk[btop --]] = 0;while (utop > ulst) num[ustk[utop].u] -= num[ustk[utop].v], f[ustk[utop].v] = ustk[utop].v, d[ustk[utop].v] ^= ustk[utop].c, -- utop; } signed main() {n = read(), m = read();for (int i = 1; i <= n ; ++ i) num[i] = 1, f[i] = i;for (int i = 1; i <= m ; ++ i) {int u = read(), v = read(), c = read();Map[MP(u, v)] = MP(0, c);}int Case = read(), num = 0;for (int i = 1; i <= Case ; ++ i) {int opt = read(), x = read(), y = read(), c;if (opt == 1) c = read(), Map[MP(x, y)] = MP(i, c);if (opt == 2) update(1, 0, m, Map[MP(x, y)].fi, i, (Cnode){x, y, Map[MP(x,y)].se}), Map.erase(MP(x, y));if (opt == 3) Q[i].PB(((Qnode){++ num, x, y} ));}for (auto t : Map) update(1, 0, m, t.se.fi, m, (Cnode){t.fi.fi, t.fi.se, t.se.se});solve(1, 0, m);for (int i = 1; i <= num; ++ i) printf("%d\n", Ans[i]);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF938G Shortest Path Queries(线性基，线段树分治，并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。