2020-2021:teams:legal_string:jxm2001:数据结构优化建图

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:数据结构优化建图 [2021/02/11 09:58]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数据结构优化建图 [2021/02/11 16:20] (当前版本)
jxm2001
@@ 行 130: / 行 130: @@
 </code>
 </hidden>
+==== 例题二 ====
+[[https://www.luogu.com.cn/problem/P6348|洛谷p6348]]
+=== 题意 ===
+$n$ 个点的无向图。给定中连边方式 $(a,b,c,d)$ 表示编号为 $[a,b]$ 的点与编号为 $[c,d]$ 的点之间连一条边权为 $1$ 的边。
+求单点源最短路。
+=== 题解 ===
+这里仅考虑单向边，双边边等价于两条单向边。
+事实上，只需要建立虚点 $u,v$，然后 $[a,b]\to u$ 和 $v\to [c,d]$ 连一条边权为 $0$ 的边，然后 $u\to v$ 连一条边权为 $1$ 的边即可。
+建完图 $01\text{bfs}$ 即可，时间复杂度 $O(m\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,Inf=1e9;
+struct Edge{
+	int to,w,next;
+}edge[MAXN*20];
+int head[MAXN*10],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+int lef[MAXN<<2],rig[MAXN<<2],Tree1[MAXN<<2],Tree2[MAXN<<2],node_cnt;
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	int M=L+R>>1;
+	if(L==R){
+		Tree1[k]=Tree2[k]=M;
+		return;
+	}
+	Tree1[k]=++node_cnt,Tree2[k]=++node_cnt;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	Insert(Tree1[k],Tree1[k<<1],0);Insert(Tree1[k],Tree1[k<<1|1],0);
+	Insert(Tree2[k<<1],Tree2[k],0);Insert(Tree2[k<<1|1],Tree2[k],0);
+}
+void AddEdge1(int k,int L,int R,int v,int w){
+	if(L<=lef[k]&&rig[k]<=R)
+	return Insert(v,Tree1[k],w);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)
+	AddEdge1(k<<1,L,R,v,w);
+	if(mid<R)
+	AddEdge1(k<<1|1,L,R,v,w);
+}
+void AddEdge2(int k,int L,int R,int v,int w){
+	if(L<=lef[k]&&rig[k]<=R)
+	return Insert(Tree2[k],v,w);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=L)
+	AddEdge2(k<<1,L,R,v,w);
+	if(mid<R)
+	AddEdge2(k<<1|1,L,R,v,w);
+}
+void Init(int n){
+	node_cnt=n;
+	build(1,1,n);
+}
+int dis[MAXN*10];
+int main()
+{
+	int n=read_int(),m=read_int(),s=read_int();
+	Init(n);
+	while(m--){
+		int a=read_int(),b=read_int(),c=read_int(),d=read_int(),u,v;
+		u=++node_cnt,v=++node_cnt;
+		AddEdge2(1,a,b,u,0);
+		AddEdge1(1,c,d,v,0);
+		Insert(u,v,1);
+		u=++node_cnt,v=++node_cnt;
+		AddEdge2(1,c,d,u,0);
+		AddEdge1(1,a,b,v,0);
+		Insert(u,v,1);
+	}
+	_rep(i,1,node_cnt)dis[i]=Inf;
+	deque<int> q;
+	dis[s]=0;
+	q.push_back(s);
+	while(!q.empty()){
+		int u=q.front();q.pop_front();
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(dis[u]+edge[i].w<dis[v]){
+				dis[v]=dis[u]+edge[i].w;
+				if(edge[i].w)q.push_back(v);
+				else q.push_front(v);
+			}
+		}
+	}
+	_rep(i,1,n)
+	enter(dis[i]);
+	return 0;
+}
+</code>
+</hidden>

2020-2021/teams/legal_string/jxm2001/数据结构优化建图.1613008686.txt.gz · 最后更改: 2021/02/11 09:58 由 jxm2001