Coursera - Algorithm (Princeton) - 习题与解答 - Week 9

Week 9

Fattest path.

问题

Given an edge-weighted digraph and two vertices $s$ and $t$, design an $E\log E$ algorithm to find a fattest path from $s$ to $t$ The bottleneck capacity of a path is the minimum weight of an edge on the path. A fattest path is a path such that no other path has a higher bottleneck capacity.

思路（未找到正确答案）

最大流+最短路

设计

应该是Dijkstra吧，就是寻找扩展路径的时候使用，应该是，网上没有合适的解释。

Perfect matchings in k-regular bipartite graphs.

问题

Suppose that there are $n$ men and $n$ women at a dance and that each man knows exactly $k$ women and each woman knows exactly k k