P6822随笔题解

本文已在博客园同步发布。
注意此为个人题解，并非转载于洛谷。
[PA 2012 Finals] Tax

题目大意

给定一个 \(n\) 个点 \(m\) 条边的无向图，定义路径的代价如下：
经过一个中间点时，代价为 \(max(\) 进入该点的边权, 离开该点的边权 \()\)。
起点 \(1\) 的代价为离开起点的边权
终点 \(n\) 的代价为进入终点的边权
求从点 \(1\) 到点 \(n\) 的最小代价。
数据范围： \(n\le10^5,m\le2\times10^5,1\le c\le10^6,n\le10^5,m\le2\times10^5,1\le c\le10^6\)
算法分析

这道题与普通最短路最大的不同在于：代价不是边权之和，而是相邻两条边权取  后再求和。也就是说，代价取决于边的组合而非单条边。
这导致我们无法直接在原图上跑 Dijkstra，由于到达同一个点时，从哪条边进来会影响后续的代价计算，状态不能简单合并。
化边为点

既然代价取决于边的组合，一个自然的想法是：把原图的每条边看作新图的一个点，两条边如果在原图中首尾相连（即存在公共端点），就在新图中连边，边权为两条边权值的 。
具体操作：
1. 将每条无向边 \(u,v,w\) 拆成两条有向边：\(u\rightarrow v\) 和 \(v\rightarrow u\)。
2. 对于原图中两条有向边 \(a:u\rightarrow v\) 和 \(b:v\rightarrow u\)(\(a\) 的终点 \(b\) 的起点)，在新图中从点 \(a\) 向点 \(b\) 连一条有向边，权值为 \(max(a_w,b_w)\)。
3. 新建超级源点 \(S\)：从 \(S\) 向全部从点 \(1\) 出发的有向边连边，权值为该边的边权(起点代价)。
4. 新建超级汇点 \(T\)：从全部指向点 \(n\) 的有向边向 \(T\) 连边，权值为该边的边权(终点代价)。
5. 在新图上跑 \(S\rightarrow T\) 的最短路即为答案。
但是给你个菊花图那你不就炸了。
差分优化建图

我们必要把每个点周围的边压缩到原来的一半。
焦点观察： 对于原图某个点 \(v\)，设其全部出边按边权从小到大排序为 \(e_1,e_2,…,e_k\)(权值分别为 \(1_w\le 2_w\le⋯\le k_w\))。
若从边 \(e_i\) 进入 \(v\)，从边 \(e_j\)​ 离开 \(v\)(\(i\le j\))，则代价为 \(max⁡(i_w,j_w)=j_w\)。这个值可以拆解为：
\(j_w=i_w+(i_w+1−i_w)+(i_w+2−i_w+1)+⋯+(j_w−j_w−1)\)
建图方法： 对每个点 \(v\) 的全部出边按权值排序后：
相邻两条边 \(e_i\rightarrow e_i+1\)​ 连一条有向边，权值为 \(wi+1−wi\)(正向差分边)。
相邻两条边 \(e_i+1\rightarrow e_i\)​ 连一条有向边，权值为 \(0\)(反向零权边)。
对于每条有向边 \(u\rightarrow v\)(权值 \(w\))，从其反向边 \(v\rightarrow u\) 向 \(u\rightarrow v\) 连一条权值为 \(w\) 的边(表示进入该点时必要付出的基础代价)。
为什么这样是对的？
假设从边 \(p\) （权值 \(p_w\)​ ）进入点 \(v\)，要从边 \(q\)(权值 \(q_w\))离开：
若 \(p_w\le q_w\)： 先从反向边走到 \(p\) （代价 \(p_w\)​ ），然后沿着正向差分边一路走到 \(q\)，总代价 \(=p_w+(q_w−p_w)=q_w=max⁡(p_w,q_w)\)。
若 \(p_w>q_w\)： 先从反向边走到 \(p\) （代价 \(p_w\)​ ），然后沿着反向零权边走到 \(q\)，总代价 \(=p_w+0=p_w=max⁡(p_w,q_w)\)。
这样，每个点周围的边数降了一半，总边数为 \(O(m)\) 级别。
再跑一遍最短路就没啦！
时间复杂度分析

前面都说完了也没啥好说的了。
后记

不要像作者一样懒，\(w_a\) 打成 \(a_w\) 干脆后面就照样写算了。

免责声明：如果侵犯了您的权益，请联系站长及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金.