HDU 5889 Barricade 最大流最小割+BFS

ACM/ICPC 2016 青岛网络赛赛题 Barricade

题意

有图G(N, M),每条边具有相同的长度和不同的权值。现在有敌人从点N沿最短长度路径到点1。现在要求在部分边上设置障碍,使敌人无论怎么走总能碰到障碍,求这些切断的边的最小权值之和。

思路

分析

因为敌人走最短路径,所以要建立新图,新图中只能保留死路和最短路径。因为每条路的长度都相等,所以可以采用bfs来寻找最短路径。在建立新图之后对新图用网络流即可。
从点N开始使用dis记录到各点最短路。当bfs到点x,尝试使用点x松弛所有相连点i并在新图中添加路径(x,i);但当bfs到点1并且点当前点x的长度大于dis[i](广度优先搜索总是最短路的),则不使用该点更新dis。
这样得到的图只含有死路(在得到dis[i]前bfs的部分)和最短路径。
代码

需要注意的地方

有几个地方需要注意:

  1. 第一个是使用bfs建立新图时
  2. 第二个是这道题源是N,汇是1,是反过来的
  3. 第三个因为最短路,所以只要添加单向边就好。
  4. 在bfs更新dis的时候我把u和v搞反了