https://www.cnblogs.com/31415926535x/p/11611801.html
偶然看到的這個東西，可以說是第一次見到圖論+資料結構的題了，，這題代碼很簡單，細節處理一下就沒啥了，，，主要是一步一步的思路的推導很不錯，，
cf-786 Legacy
cf-786 Legacy
以前做過的圖論題就只是圖論題，從來沒想過和資料結構-線段樹扯上關系，，
這題也算是一個經典的例題了吧，，應該就是那種知道的做過的就會做出來的型別，，
思路分析
題意很簡單，就是一個簡單的圖，，給出一些建圖的方式，，但是，和以往不同的是，以前的邊的關系給的都是點與點間的關系，，這種題給的方式是區間，，比如說 u->[l, r] 表示的就是u和這個區間的所有點間都有一條邊，，因為一個點也可以看成一個只有自己的區間，，所以我們可以將這類關系統一看成 \([l_1, r_1]->[l_2, r_2]\) ，，
容易想到的方法就是直接兩個 for 上去，，建出每一條邊，，資料很小的時候沒問題，，，但是當n 很大時，，顯然建圖的復雜度可能就是 \(O(n^2m)\) 這樣不管求最短路就炸了，，，
一種優化的方法是我們在這兩個區間之間加一個點，，這樣前面的區間（成為出區間）和后面的一個區間（稱為入區間）都和這個點 \(p\) 連，，也就是 \(\forall u \in [l_1, r_1]: addedge(u, p, w)\) 而 \(\forall v \in [l_2, r_2]: addedge(p, v, 0)\) （ \([l_1, r_1]-_u>p-_0>[l_2, r_2]\) ） 這樣子就可以降一維的建圖，，復雜度就是 \(O(2nm)\) ，，但是這樣還是很高，，
這時的建圖是線性的建圖方式，，線性+區間==線段樹？？！！，，這是我做這道題學習到的最有價值的一個處理方式，，在降了一維之后，雖然是線性的建圖，，但是點還是很多，，而線段樹恰好可以用很少的子區間來表示原來的區間，，，如果將線段樹中的每一個表示的區間看成一個點，，那么我們就可以用很少的點來建圖，，，這樣就可以將上面的n次的建圖降下去，，，
那么這時的問題就變成了該如何利用線段樹來處理，，
我們需要兩棵線段樹，，一棵看成 入樹 另一棵看成 出樹 ，，
首先我們的目的是用少量的區間來表示原來的很大的區間，以達到用很少的點來表示原來的所有點，，優化的問題用線段樹解決了，，但是，如何正確的表示原來的所有點呢，，，
線段樹的每一個節點表示一個區間，，這個節點可以表示他下面的所有點，，也就是說，，我們可以從上向下的看，，定義選擇了一個節點，，就選擇了下面的所有點，，，按照這個思想，入樹中的一個節點要向其兒子連一條指向兒子的有向邊，，也就是說，，入樹中所有的邊指向下，，用 down 表示
同理，，對于出樹，，我們要保證在一個節點要能表示所有的點，，于是就是一個節點下的所有節點都要指向它，，，這樣看這棵樹就是一個向上的樹，，用 up 表示，，
這個樣子的：
這樣最后在這樣初始圖加上題目給的一些條件的邊跑一邊最短路就可以了，，
加上題目的邊后的圖大致是這樣的：
實際上，，這里的線段樹的作用只是一個建樹和查詢其子區間的作用，，這個思想有點像是分塊，，，只要能找到一個合理的區間分塊，，用一些合理的、數量少的區間表示原來的區間，，就能達到減少點數的作用，，，，而線段樹恰好是一個熟悉的、好操作的區間劃分模型，，所以很多人都對于 區間圖的最短路問題都是套一個線段樹的板子，，
回到這道題，，題目的加邊方式只有 點對區間 和 區間對點 兩種，，所以我們可以先預留出那n個點，，可以想象成放在這兩棵樹之間的一排點（不用再將兩棵樹的葉子節點相連，，），，，
然后再處理出出樹、入樹的邊后，，對于 u->[l, r] 和 u->v 的邊，，從點 u 向入樹的符合條件的節點連邊即可，，因為之前說的入樹保證了每一個節點是可以到其下面的葉子節點的，，所以我們這樣連邊就相當于是點 u 向區間的每一個點連邊，，，
同理對于 [l, r]->u 這樣的邊，，我們將入樹的對應的節點和點 u 相連，，這樣就保證入樹中這個區間下的葉子節點可以通過這些區間到點 u ，，這樣也滿足了題意的同時減少的連邊的復雜度，，，
最后跑最短路，，前n個點的 dis[i] 即為源圖的那些點的最短路，，，
于是我們通過加點減邊的方式減小了建圖的時間復雜度，，
關于處理出樹、入樹的操作，，也就是線段樹的建樹程序，，其實線段樹并不維護任何資訊，，我們只是用它自己每個節點表示一個區間這個自身的性質，，所以為了建圖，，，我們需要對每一個節點連一些邊，，，也就是用一個 id[rt] 標記一下每一個節點的標號即可，，，
最后的代碼：
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 1e6 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
struct Dijkstra
{
struct edge
{
int to, nxt; ll w;
}edge[maxm];
int tot, head[maxm];
void init()
{
tot = 0;
memset(head, -1, sizeof head);
}
void addedge(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v; ll w;
node(){}
node(int _v, ll _w):v(_v), w(_w){}
const bool operator<(const node &r)const
{
return w > r.w;
}
};
bool vis[maxn];
ll dis[maxn];
priority_queue<node> pq;
void dijkstra(int s, int n)
{
memset(vis, false, sizeof vis);
memset(dis, inf, sizeof dis);
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
node t;
int u;
while(!pq.empty())
{
t = pq.top(); pq.pop();
u = t.v;
if(vis[u])continue;
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > t.w + w)
{
dis[v] = t.w + w;
pq.push(node(v, dis[v]));
}
}
}
}
void print(int n)
{
for(int i = 1; i <= n; ++i)cout << (dis[i] == linf ? -1 : dis[i]) << " ";cout << endl;
}
}dijkstra;
int cnt;
struct segmentTree
{
int id[maxn]; // 節點標記陣列，，記錄線段樹中每一個節點的標號，，從 n+1 開始，，前面的n個是原來的點
void build(int rt, int l, int r, bool flag) // 建樹（建圖，，flag == false 表示是一棵入樹，邊向下，節點指向兒子
{
id[rt] = ++cnt;
if(l == r)
{
int u = id[rt];
int v = l;
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, flag);
build(rt << 1 | 1, mid + 1, r, flag);
// pushup
int u = id[rt];
int v = id[rt << 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
u = id[rt];
v = id[rt << 1 | 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
void addedge(int rt, int l, int r, int U, int L, int R, ll w, bool flag) // flag == false 表示 u->[l, r] ，，
{
if(l > R || L > r)return;
if(L <= l && r <= R)
{
int u = U;
int v = id[rt];
if(flag)swap(u, v);
dijkstra.addedge(u, v, w);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid, U, L, R, w, flag);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r, U, L, R, w, flag);
return;
}
}down, up;
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n, q, s;
cin >> n >> q >> s;
cnt = n; // 出樹、入樹等的輔助點的標記從n+1開始
dijkstra.init();
down.build(1, 1, n, false);
up.build(1, 1, n, true);
int t, u, v, w, l, r;
while(q--)
{
cin >> t;
if(t == 1)
{
cin >> u >> v >> w;
l = r = v;
t = 2;
}
else
cin >> u >> l >> r >> w;
if(t == 2)
down.addedge(1, 1, n, u, l, r, w, false); // u -> [l, r]
else
up.addedge(1, 1, n, u, l, r, w, true); // [l, r] -> u
}
dijkstra.dijkstra(s, cnt);
dijkstra.print(n);
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
以上的一些內容和圖片參考這個dalao的博客
最后的AC代碼的大致思路是參考葫蘆爺大佬的板子
hdu-5361In Touch
hdu-5361In Touch
差不多的題，，貌似解法有很多，，如果用這種方法來解的話，，只用一棵入樹就行了，，，還有可能得改一改寫的姿勢，，，（多載w爆int一晚上沒看出來的怕不是只有我一個了吧，，，emmmm
AC_1
#include <bits/stdc++.h>
// #include <iostream>
// #include <queue>
// #include <cstring>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
inline int read() //快讀
{
int ans=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n;
struct edge
{
int to, nxt;
ll w;
}edge[maxm];
int tot, head[maxn << 3];
void init(int n)
{
tot = 0;
for(int i = 0; i <= n; ++i)head[i] = -1;
}
void ADDEDGE(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v;
ll w;
node(){};
node(int _v, ll _w): v(_v), w(_w){};
const bool operator<(const node &r)const{
return w > r.w;
}
}tmp;
bool vis[maxn << 3];
ll dis[maxn << 3];
priority_queue<node> pq;
void dijkstra(int s, int n)
{
for(int i = 0; i <= n; ++i)dis[i] = linf;
for(int i = 0; i <= n; ++i)vis[i] = false;
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
while(!pq.empty())
{
tmp = pq.top(); pq.pop();
if(vis[tmp.v])continue;
vis[tmp.v] = true;
for(int i = head[tmp.v]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(dis[v] > dis[tmp.v] + edge[i].w)
{
dis[v] = dis[tmp.v] + edge[i].w;
pq.push(node(v, dis[v]));
}
}
}
}
int cnt;
void build(int rt, int l, int r)
{
if(l == r)
{
cnt = max(cnt, rt + n);
ADDEDGE(rt + n, l, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
ADDEDGE(rt + n, (rt << 1) + n, 0);
ADDEDGE(rt + n, (rt << 1 | 1) + n, 0);
}
int L, R, W, U;
void addedge(int rt, int l, int r)
{
if(L > r || l > R)return;
if(L <= l && r <= R)
{
ADDEDGE(U, rt + n, W);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r);
}
int l[maxn], r[maxn], c[maxn];
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// int t; cin >> t;
// int t; scanf("%d", &t);
int t; t = read();
while(t--)
{
// cin >> n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)l[i] = read();
for(int i = 1; i <= n; ++i)r[i] = read();
for(int i = 1; i <= n; ++i)c[i] = read();
init(n << 3);
cnt = 0;
build(1, 1, n);
for(int i = 1; i <= n; ++i)
{
U = i;
L = i + l[i]; R = i + r[i]; W = c[i];
addedge(1, 1, n);
L = i - r[i]; R = i - l[i];
addedge(1, 1, n);
}
dijkstra(1, cnt);
printf("0");
for(int i = 2; i <= n; ++i)
printf(" %lld", (dis[i] == linf ? -1 : dis[i]));
puts("");
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
AC_2
（不加快讀也沒事，，，就是不能memset，，，卡memset好惡心，，，，
#include <bits/stdc++.h>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
inline int read() //快讀
{
int ans=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
struct Dijkstra
{
struct edge
{
int to, nxt;
ll w;
}edge[maxm];
int tot, head[maxn << 3];
void init(int n)
{
tot = 0;
// memset(head, -1, sizeof head);
for(int i = 0; i <= n; ++i)head[i] = -1;
}
void addedge(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v; ll w;
node(){}
node(int _v, ll _w):v(_v), w(_w){}
const bool operator<(const node &r)const
{
return w > r.w;
}
};
bool vis[maxn << 3];
ll dis[maxn << 3];
priority_queue<node> pq;
void dijkstra(int s, int n)
{
// memset(vis, false, sizeof vis);
// memset(dis, inf, sizeof dis);
for(int i = 0; i <= n; ++i)vis[i] = false;
for(int i = 0; i <= n; ++i)dis[i] = linf;
while(!pq.empty())pq.pop();
pq.push(node(s, 0));
dis[s] = 0;
node t; int u;
while(!pq.empty())
{
t = pq.top(); pq.pop();
u = t.v;
if(vis[u])continue;
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > t.w + w)
{
dis[v] = t.w + w;
pq.push(node(v, dis[v]));
}
}
}
}
void print(int n)
{
printf("0");
for(int i = 2; i <= n; ++i)printf(" %lld", (dis[i] == linf ? -1 : dis[i]));
puts("");
}
}dijkstra;
int cnt;
struct segmentTree
{
int id[maxn << 3];
void build(int rt, int l, int r, bool flag)
{
id[rt] = ++cnt;
if(l == r)
{
int u = id[rt];
int v = l;
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, flag);
build(rt << 1 | 1, mid + 1, r, flag);
int u = id[rt];
int v = id[rt << 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
u = id[rt];
v = id[rt << 1 | 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
void addedge(int rt, int l, int r, int U, int L, int R, ll w, bool flag)
{
if(L > r || R < l)return;
if(L <= l && r <= R)
{
int u = U;
int v = id[rt];
if(flag)swap(u, v);
dijkstra.addedge(u, v, w);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid, U, L, R, w, flag);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r, U, L, R, w, flag);
return;
}
}down; //, up;
int l[maxn], r[maxn], c[maxn];
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
int t; t = read();
while(t--)
{
int n; n = read();
for(int i = 1; i <= n; ++i)l[i] = read();
for(int i = 1; i <= n; ++i)r[i] = read();
for(int i = 1; i <= n; ++i)c[i] = read();
cnt = n;
dijkstra.init(n << 3);
down.build(1, 1, n, false);
// up.build(1, 1, n, true);
for(int i = 1; i <= n; ++i)
{
down.addedge(1, 1, n, i, l[i] + i, r[i] + i, c[i], false);
down.addedge(1, 1, n, i, max(1, i - r[i]), max(1, i - l[i]), c[i], false);
}
dijkstra.dijkstra(1, cnt);
dijkstra.print(n);
}
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
(end)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/102079.html
標籤：C++
上一篇：樹-基本概念，遍歷，表示法
下一篇：fopen