再过两（百）三（百）天就考CSP2024了，重新学一下提高的知识
part.1 图论
最短路
最短路问题，即在一个图中，寻找两个节点之间的最短路径的问题。最短路问题分为单源最短路和多源最短路
单源最短路:
给定一个起点 \(s\)，找到 \(s\) 到图中其它所有节点的最短路径长度。通常 \(div\) 表示 \(s\) 到 \(i\) 的最短路径长度，\((x,y,z)\) 表示从 \(x\) 到 \(y\) 有一条有向边，该条边的权值为 \(z\) 。
一般有两种解法：Dijkstra和SPFA（怎么会有人打dijspfa呢）
-
\(Dijkstra\)：
十分稳定且优化后复杂度是高贵的 \(O(mlogn)\)，但是不能处理负边权- 算法流程：
初始化\(d[s]=0\)
找到一个未标记过且\(d[x]\)值最小的节点\(x\)，对\(x\)进行标记
遍历\(x\)的所有出边\((x,y,z)\)，若\(d[y]>d[x]+z\)，则更新\(d[y]=d[x]+z\)
重复第\(2、3\)步，直到所有边都被标记过
- 算法原理：
当第2步找到一个未标记过且\(d[x]\)值最小的节点\(x\)时，由于在图中所有未标记的节点\(i\)的\(d[i]\)值都大于等于\(d[x]\)，若图中没有负权边，即所有边的权值为非负数，则\(d[x]\)的值不可能再被其它节点更新，因此可以用它来更新其它节点的值.当第三步\(d[y]>d[x]+z\)时，说明当前\(s\)到节点\(y\)的路径比\(s\)经过节点\(x\)和\((x,y,z)\)到达节点\(y\)的路径要长，因此要采用后者的长度来作为更短的路径。而不断重复第2、3步，就可以不断更新全局最小值，达到求出最短路径的目的。
- 优化原理：
正常会在第\(2\)步寻找全局最小值时浪费大量的时间。因此我们可以利用优先队列实现每次\(O(logn)\)地查找全局最小值
- 堆优化DIJ的代码：
#include<bits/stdc++.h> #define lC q<<1 #define rC q<<1|1 #define int long long #define INF 0x66ccff0712 #define endl "\n" #define maxm 0x66ccff #define maxn 0x6cf #define mid ((l+r)>>1) #define void inline void using namespace std; inline int read(){ int s = 0,w = 1;char ch = getchar(); while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();} while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();} return s*w; } struct SegmntTree{ int ver,Next,edge; }t[maxm]; const int N=3e5; int n,m,s,tot=0,v[N],d[N]; priority_queue< pair<int,int> > q; void add(int x,int y,int z){ t[++tot].ver=y, t[tot].edge=z, t[tot].Next=head[x], head[x]=tot; } void Splay() { memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) d[i]=2147483647; d[s]=0; q.push(make_pair(0,s)); while(q.size()){ int x=q.top().second; q.pop(); if(v[x]) continue; v[x]=1; for(int i=head[x];i;i=t[i].Next){ int y=t[i].ver,z=t[i].edge; if(d[y]>d[x]+z){ d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } } signed main(){ n=read(),m=read(),s=read(); while(m--){ int u=read(),v=read(),w=read(); add(u,v,w); } Splay(); for(int i=1;i<=n;i++) cout<<d[i]<<" "; } -
\(Spfa\):
- 算法