[ZOJ2760]How Many Shortest Path(floyd+最大流)

时间:2021-05-11 11:36:29

题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1760

题意:给你一个一个n*n(n<=100)的有向图,问你从s到t有多少条路径最短且这些路径没有边重合。

分析:

反过来想,如果我们知道哪些边是最短路径上的边,那么表明这条边必须只能走一边,于是可以把这样的边容量设为1,然后跑s到t的最大流。

于是问题的关键就是如何找出在最短路径上的边。

可以先用floyd算出每两点之间的最短路d[i][j]

如果一条边(u,v)满足d[s][u]+g[u][v]+d[v][t]==d[s][t],那么表示这条边一定在某条最短路径上,把这个边容量设为1就行了。