ZOJ 2760 How Many Shortest Path

题目大意:给定一个带权有向图G=(V, E)和源点s、汇点t,问s-t边不相交最短路最多有几条。(1 <= N <= 100)

题解:从源点汇点各跑一次Dij,然后对于每一条边(u,v)如果保证d[s][u]+d[u][v]+d[v][t]==d[s][t]就加边1,然后跑最大流就好。

然而为什么不能是d[s][u]+d[u][t]==d[s][t]呢?我给个反例好了。

比如看这个图:(这是我用Gve写的最丑的图了将就看吧)

digraph G{
    1->2[label="1"];
    1->3[label="3"];
    2->3[label="1"];
    3->4[label="1"];
    2->4[label="2"];
}

会发现(1,3)这条边也被加进去了,然后就没有然后了。

原文地址:https://www.cnblogs.com/chxer/p/4561574.html