ZOJ 2760 How Many Shortest Path (不相交的最短路径个数)

【题意】给定一个N(N<=100)个节点的有向图，求不相交的最短路径个数（两条路径没有公共边）。 【思路】先用Floyd求出最短路，把最短路上的边加到网络流中，这样就保证了从s->t的一个流一定是一条最短路，也就保证了网络流建模的正确性。 【找最短路上的边】 满足最优子结构的性质：(i, j)是最短路上的边，当且仅当dist[s][i] + edge[i][j] + dist[j][t] = dist[s][t]. 一开始想的是满足dist[s][j] = dist[s][i] + edge[i][j]就行了，不过这显然是不对的。这只满足了i点到s点是最短路，却不能保证j点到t点也是最短路，自然也保证不了(i, j)是最短路上的边。 【代码】http://paste.ubuntu.com/5887014/