Codeforces 786B Legacy (線段樹(shù)優(yōu)化建圖)

---

題意：\(n\)個(gè)點(diǎn)，有\(3\)種連邊操作：1.將\(u\)指向\(v\)；2.將\(v\)指向編號(hào)在區(qū)間\([l,r]\)的點(diǎn)；3.將\([l,r]\)中的所有點(diǎn)指向\(v\)

做法：線段樹(shù)優(yōu)化建圖。拓展一些新的節(jié)點(diǎn)來(lái)代表某些區(qū)間的點(diǎn)，然后，如果需要進(jìn)行區(qū)間\([L,R]\)連邊，那么就可以將\([L,R]\)拆成一些區(qū)間的組合，以此減少邊的數(shù)目。于是可以利用線段樹(shù)，將每個(gè)線段樹(shù)上的節(jié)點(diǎn)新建出來(lái)，連接對(duì)應(yīng)的區(qū)間即可，而因?yàn)槿绻挥幸活w線段樹(shù)不能對(duì)所有點(diǎn)跑最短路，所以我們建兩棵線段樹(shù)，一顆指向序列，另一顆從序列指出來(lái)。原本對(duì)應(yīng)的區(qū)間邊權(quán)設(shè)為0，跑最短路即可。

#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <queue> #include <cstring> #define IOS ios::sync_with_stdio(false) #define pb push_back #define Pii pair<int,int> #define Ppi pair<Pii, int> #define x first #define y second typedef long long ll; const int N = 100020; inline void read(int &x) {x = 0; int f = 1; char c = getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=x*10+c-'0';c=getchar();}x *= f; } using namespace std; bool ST; int n, q, st; struct edge {int e,w,nxt;} E[10000003]; int h[6000000], cc; void add(int u, int v, int w) {E[cc].e = v; E[cc].w = w; E[cc].nxt = h[u]; h[u] = cc; ++cc; } int ID[2][N << 2], id; void build(int p, int l, int r, int typ) {ID[typ][p] = ++id;if(!typ) for(int i = l; i <= r; ++i) add(ID[typ][p], i, 0);else for(int i = l; i <= r; ++i) add(i, ID[typ][p], 0);if(l == r) return;int mid = (l + r) >> 1;build(p<<1,l,mid,typ);build(p<<1|1,mid+1,r,typ); } void update(int p, int l, int r, int v, int L,int R, int w, int typ) {if(l == L && r == R) {if(!typ) add(v, ID[typ][p], w);else add(ID[typ][p], v, w);return;}int mid = (l + r) >> 1;if(R <= mid) update(p<<1,l,mid, v,L,R,w,typ);else if(L > mid) update(p<<1|1,mid+1,r, v,L,R,w,typ);else {update(p<<1,l,mid, v,L,mid,w,typ);update(p<<1|1,mid+1,r, v,mid+1,R,w,typ);} } struct node {int e; ll w;node(){}node(int a, ll b) {e=a;w=b;}bool operator < (const node &a) const {return w > a.w;} }; ll dis[6000001]; int vis[6000001]; void dij(int st) {for(int i = 1; i <= id; ++i) dis[i] = __LONG_LONG_MAX__;priority_queue< node > q;q.push(node(st,0)); dis[st] = 0;while(!q.empty()) {node u = q.top(); q.pop();if(vis[u.e]) continue;vis[u.e] = 1;for(int i = h[u.e]; ~i ; i = E[i].nxt) {int v = E[i].e; ll w = E[i].w;if(dis[u.e] != __LONG_LONG_MAX__ && dis[v] > dis[u.e] + w) {dis[v] = dis[u.e] + w;q.push(node(v,dis[v]));}}} } int main() {read(n), read(q), read(st);memset(h, -1, sizeof(h));id = n;build(1,1,n,0); // tree -> []build(1,1,n,1); // [] -> treefor(int opt,u,v,w,l,r,i = 1; i <= q; ++i) {read(opt);if(opt == 1) read(u), read(v), read(w), add(u, v, w);else if(opt == 2) read(v), read(l), read(r), read(w), update(1,1,n, v,l,r,w, 0);else read(v), read(l), read(r), read(w), update(1,1,n, v,l,r,w, 1);}dij(st);for(int i = 1; i <= n; ++i) printf("%lld ",dis[i] == __LONG_LONG_MAX__ ? -1 : dis[i]); puts(""); }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/10333247.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 786B Legacy (线段树优化建图)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。