口胡 HDU - 3416 Marriage Match IV

link
题意，求有多少条最短路径，要求边不能够重叠。
乍一看将每条边容量弄成 \(1\) 跑最大流之类的，但此题要求最短路。此题瓶颈在于，我们不知道选什么边的组合是最短路。于是就有了这个 trick：
首先，我们选的边一定在某一个最短路径上。于是先跑个最短路，检查每条边是否最优。（即 \(最短路[x]+val(x,y)\) 是否为 \(最短路[y]\)）。如果是，那么这条边可以延续最短路，即这条边目前为止一定是合法的，数学归纳，整个过程就是合法的了。同时可以证明任意的一条路都可以通过这些边走出来，所以这样一定是完备的。将其容量设为 \(1\)，否则设为 \(0\)，跑最大流即可。