HDU 5294 Tricks Device (最短路+网络流)

HDU 5294 Tricks Device (最短路+网络流)

题意:n个点,m条边,构建有权无向图。求出删去最少条边数没有最短路,以及删出最多条边,使最短路的长度不变。 思路:先处理出最短路,然后使用结果的dis数组,若dis[v]-dis[u] = w(u,v),则该路就是最短路经中的一条边。建出最短路径之后跑最大流,流量是有多少边权相同的重边,跑出来就是最小割,也就是阻断所有最短路的最小花费。最后再跑最短路,边权为...
07月20日 325
  1. .01
  2. .02