再过两（百）三（百）天就考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\):

  • 算法