ZOJ 2760 HOW MANY SHORTEST PATH (不相交的最短路径个数)
【题意】给定一个有N（N<=100）个节点的有向图，求不相交的最短路径的个数（两条路径没有公共边）。 【思考】首先用Floyd求最短路径，将最短路径上的边加入到网络流中，保证从s->t的一个流一定是最短路径，这样也保证了网络 流动建模是正确的性。 【求最短路径上的边】满足最优子结构的性质：(i,j)是最短路径上的边当且仅当dist + edge + dist = dist。 起初，我以为 dist = dist + edge 就可以了，但这显然是错误的。 这只是满足点 i 到点 s 是最短路径，但不保证点 j 到点 t 也是最短路径，自然也不保证 (i, j) 是最短路径上的边 .( given a directed graph with n (n < = 100) nodes, find the number of disjoint shortest paths (two paths have no common edge). first, use Floyd to find the shortest path and add the edge on the shortest path to the network flow to ensure that a flow from S - > t must be the shortest path, which also ensures the correctness of network flow modeling. satisfies the properties of the optimal substructure: (I, J) is the edge on the shortest path if and only if dist + edge + dist = dist . At first, I thought dist = dist + edge , but it was obviously wrong. This only satisfies that point I to point s is the shortest path, but it does not guarantee that point J to point t is also the shortest path. Naturally, it does not guarantee that (I, J) is the edge on the shortest path
)
页:
[1]