【线性规划与网络流24题】最小路径覆盖问题

其实题目里的提示并没有看懂在干嘛。。

首先把每个点复制一份,建一张二分图,然后对于每一条有向边(a,b)连一条从左边的a点到右边的b点的边。然后跑二分图匹配就可以了。那么每一条匹配边相当于选出了原图中的一条边,每一条边相当于把两个点合并了。所以答案=点数-匹配数。

说点什么

  Subscribe  
提醒