「珍貴歷史資料鑒賞」CF786B 題解
寫在前面
偶然翻到一篇 2019-08-07 18:58 寫的未發布的題解。
給大家找點樂子玩。
正文
知識點:線段樹優化建圖
線段樹優化建圖
用於解決
類似 從 x 向區間[L,R]的
區間連邊問題
原圖:
1 2 3 4
向其中添加一系列虛點 ,
並將虛點與實點 , 虛點與虛點 連邊,
將添加的邊,的邊權值設為0 之後:
o
/ \
o o
/ \ / \
1 2 3 4
形成一棵滿二叉樹
對於這棵滿二叉樹,
可以將其當作一棵線段樹,
來進行一系列的操作:
-
對於 從 x 向區間[L,R]連邊操作:
由於新添加的邊權全為0
所以只需要將 x 與
"管轄" 著 [L,R] 區域的虛點連線即可
可以類比線段樹的區間查詢,
進行遞歸查詢,要連接的邊數,
由 R-L級別 ,轉化為了log(R-L)級別 -
對於 從 區間[L,R] 向 x 連邊操作:
逆向操作
考慮反向連邊即可
同時在初始化時,
也要注意 初始化反向的邊 -
對於 從x 向 y連邊操作
直接連接即可
演算法實現:
先進行兩次 初始化建樹操作
分別處理正向與反向的 ,
與虛點之間的連邊,
將其設置為0.
然後對於每種連邊操作,
按照上述法則,
將x與實點/虛點 連邊
最後跑一遍最短路即可
注意的一些小點:
1.為了不影響實點之間的連邊
虛點,即線段樹上的點 的編號,
從n+1開始編號
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
const int MARX = 3e5+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
//============================================
struct edge
{
int u,v,w,ne;
}e[MARX<<4];//各邊
int n,q,start;//輸入的初始變數
std:: queue <int> qu;//spfa的隊列
int num,head[MARX];//建圖變數
int cnt,root1,root2,ls[MARX],rs[MARX];//線段樹變數 (ls為左兒子,rs為右兒子)
ll dis[MARX];//spfa 變數
//============================================
inline void add(int u,int v,int w)
{
e[++num].v=v,e[num].u=u,e[num].w=w;
e[num].ne=head[u],head[u]=num;
}
void build1(int &s,int l,int r)//初始化 從父親向兒子的0邊
{
if(l==r)//遞歸向下,直到 到達葉子部的 實點,
{
s=l;//實點的編號不變
return;
}
s = ++cnt;//更新當前虛點的編號
int mid = (l+r)>>1;
build1(ls[s],l,mid);//遞歸左右子樹
build1(rs[s],mid+1,r);
add(s,ls[s],0);//向下連0邊
add(s,rs[s],0);
}
void build2(int &s,int l,int r)//類比build1,進行反向連0邊
{
if(l==r)
{
s=l;
return;
}
s = ++cnt;
int mid = (l+r)>>1;
build2(ls[s],l,mid);
build2(rs[s],mid+1,r);
add(ls[s],s,0);
add(rs[s],s,0);
}
int L,R;//要操作的左右區間
void updata(int s,int l,int r,int u,int w,int type)//s:當前點編號; l,r:當前點s管轄區間 ; type:操作的種類
{
if(L<=l && r<=R)//操作區間 包含 當前區間
{
if(type==2) add(u,s,w);//按照種類,進行連邊操作.
else add(s,u,w);
return ;
}
int mid=(l+r)>>1;
if(L<=mid) updata(ls[s],l,mid,u,w,type);//遞歸進行操作
if(mid<R) updata(rs[s],mid+1,r,u,w,type);
}
void spfa(int start)//他死了
{
memset(dis,0x3f,sizeof(dis));
dis[start]=0;qu.push(start);
while(!qu.empty())
{
int u=qu.front(); qu.pop();
for(int i=head[u];i;i=e[i].ne)
{
int v=e[i].v,w=e[i].w;
if(dis[u]+w < dis[v])
{
dis[v]=dis[u]+w ;
qu.push(v);
}
}
}
}
//============================================
signed main()
{
scanf("%d%d%d",&n,&q,&start);
cnt=n;//為不影響實點之間的連邊 , 虛點,從n+1開始編號
build1(root1,1,n),build2(root2,1,n);//初始化
for(int i=1;i<=q;i++)
{
int opt,u,v,w;
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);//直接連接
}
else
{
scanf("%d%d%d%d",&u,&L,&R,&w);
updata((opt==2?root1:root2),1,n,u,w,opt);//按照種類,進行操作
}
}
spfa(start);
/*
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=e[j].ne)
printf("%d %d %d\n",i,e[j].v,e[j].w);
*/
for(int i=1;i<=n;i++) printf("%lld ",dis[i]<INF?dis[i]:-1);
}
