P6822 [PA 2012 Finals] Tax 题解
题目大意
可恶，我们老师竟然把紫题放到了模拟赛里。
题目传送门
原题中题意说的很清楚了。
思路
转化问题
首先先新建两条边，使原题点到点的问题转化成边到边的问题。
可以连接一条从 0 0 0 到 1 1 1，长度为 0 0 0 的边，设这条边为 0 0 0 号边。
还可以连接一条从 n n n 到 0 0 0，长度为 0 0 0 的边，设这条边为 m + 1 m+1 m+1 号边。
这样原题就变为了从 0 0 0 号边到 m + 1 m+1 m+1 号边的最小代价。
化边为点
边到边的问题有一种常见做法：化边为点。
即把每条边看做一个点，将边与边之间连边，从起点边向终点边求最短路得到答案。
这道题也可以这么做，可以将首尾相连的两条边相连（即两条边有共同的节点），边权为两条边长度的最大值（原题中的代价）。
优化建图
但这样有个很明显的缺点，如果原图是菊花图，那么新图的边数最多可达到 m 2 m^2 m