贺题记录

• 物流运输 典 最短路+DP
  这题想出状态与方程的关键之一 在于考虑决策 (同一路径走多少天)

• 路径统计 最短路径数

• Johnson全源最短路 模板 最短路之Johnson的 \(\text{O(NMlogN)}\)全源最短路 (包含 SPFA, dijkstra的模板)

• 基础最短路练习题 最短路
  求异或和最短路, 数据保证任何环的异或和为 0

• 最短环 典 最短环问题

• 洛谷: 电话线路 典 难 多解
  \(大意\) 在无向图上求出一条从1到N的路径, 使路径上第K+1大的边权尽量小
  (待补)

• 洛谷: 最优贸易 典 多解 分层图 or 反向图 or 缩点+拓扑序DP　（值得一做)

  简析

  \(大意\) 给定 单双混向的 点带权图, 从 1 出发到 n, 每个结点可重复经过.
  路径上的两个点p, q(先经过p, 后q), 使 \(V_q - V_p\)的值最大, 求该最大值.
  (注: p, q可以为同一个结点, 则此时值为 0)　(\(1≤n≤100000;1≤m≤500000\))
  \(简析\)

  1. 分层
     发现, 在p上买入后, 所有结点便只能卖出. 换句话说, 通过买入, 进入到另一层 -- 卖出层.
     
     这题 要存\(3n\)个结点和\(3m+n\)条边, 而内存限制64MB, 也足够.
     那要是内存不够怎么办呢? 由于第一层到第二层的边权 是 第二层到第三层连的 边权的 相反数. 所以我们可以只建一层, 然后每个结点向自身连边..(见代码)
     \(AC代码\): 分层图解法 由于有负权边, 要用SPFA (这题SPFA没被卡..)
  2. 反向图
     在原图上, 求 \(f[x]\): 从 1 到 x 的所有路径中, 能够经过的权最小权值;
     在反图上, 求\(g[x]\): 从 x 到 n 的所有路径中, 能够经过的最大权值(反图上为 n 到 x).
     答案就是 \(\max g[x]-f[x]\)
     \(AC代码\): 反向图
  3. 缩点+拓扑序DP (待补)

• 洛谷: 道路与航线 典 SPFA的优化 or 缩点+dijkstra

  简析

  \(大意\) 给定一种带权图, 它有两种边: 1. 道路, 双向的且均是正权 2. 航线, 单向的且均是负权. 求单源最短路
  \(简析\)

  1. SPFA优化 blog1 .//blog2 (该博客图挂了)

     • SLF(酸辣粉): 入队时, 当前元素比队头小就插入队头，否则插入队尾 (注意要判断队列是否为空!)
       -LLL优化: 不断 轮转, 直到 队列中dis的平均值 大于 当前dis值.

     • (网上引用)一般来说, SLF优化效率是 15%~20%; 而SLF+LLL 则约为大概50%.

     AC代码: SLF+LLL
     本题实测: SLF约3100ms. SLF+LLL约3500ms. LLL TLE..(为什么SLF+LLL反而慢了呢???)

  2. 缩点+dijkstra. 不考虑负权边, 此时图变成若干个连通块. 对每个连通块进行dijkstra. 利用负权边进行转移　(详情见代码)
     AC代码 注意: 一定要提前把 入度为0的入队! 否则有些可达连通块的入度可能不会降为 0
     

• 洛谷: Sorting It All Out 传递闭包 + Floyd

  简析

  \(大意\) 逐步 给出n个变量和m个大小关系不等式, 判断哪步后 出现矛盾或可确认所有变量的大小关系. 最后要判断能否确定所有变量的关系.
  \(简析\)
  　若 \(A_i < A_j\) 则 f[i, j]=1, 否则 f[i, j]=0.
  　用Floyd传递闭包. 完成后, 若\(f[i,j]=f[j,i]=1\) 则矛盾! 若\(f[i,j]=f[j,i]=0\) 则目前不能判断\(A_i\)与\(A_j\)之间的关系.
  AC代码

• 洛谷: 最小环 典 Floyd 最小环

  简析

  \[\min_{i≤i<j<k}{d[i,j]+a[j,k]+a[k,i]} \]

  \(AC代码\) 　注: 洛谷上的最小环不用输出路径

• 洛谷: 牛站 典 难 二进制拆分+倍增 or Bellman-Ford+吸氧 . 离散化　（非常值得一做）

  简析

  \(大意\) 给定 不超过100条边组成的 无向图, 求起点到终点 恰好经过 N 条边的最短路(可重复经过)
  \(简析\)

  1. Bellman-Ford+吸氧 将N作为 BFord 的外层循环上界. (UVA不准吸氧, 此法不可行)

     void Bellman_Ford(){
     	memset(dis, 0x3f, sizeof(dis)); dis[S]=0;
     	REP(k, 1, K){   // 扩展到 第k条边
     		memcpy(tdis, dis, sizeof(dis)); // 这里要在 "之前的"最短距 上拓展. 来保证每次只拓展一条边.
     		memset(dis, 0x3f, sizeof(dis));
     		REP(i, 1, m){
     			int u=e[i].u, v=e[i].v, w=e[i].w;
     			dis[u]=min(dis[u], tdis[v]+w);  // 若这里不用 tdis, 则可能会一次拓展两次 u->v, v->u
     			dis[v]=min(dis[v], tdis[u]+w);
     		}
     	}
     }
     

     AcWing上的AC代码: BFord+吸氧
  2. 二进制拆分 + 倍增大佬blog or 用了类快速幂的大佬的博客
     粗略地说: 若矩阵\(A^m\)保存任意两点之间恰好经过m条边的最短路, 则$$\forall i,j∈[1,P],　（A^{r+m})[i,j]=\min_{1≤k≤P} {(A^r)[i,k]+(Am)[k,j]}$$
     该式满足结合律, 因此可以用 快速幂 计算.
     \(AC代码\)(未用快速幂)