HDU5876SparseGraph

题目大意&＃xff1a;

给你一个完全图让你删除给出的这些边形成新的图&＃xff0c;问你在新的图上的s点到其它所有点的距离。

解题思路&＃xff1a;

BFS乱搞...

补图的BFS的问题虽然很经典&＃61; &＃61;不过确实还是第一次做。很方。

用一个map来保存邻接的信息。因为最多20000&＃xff0c;很坑的是比赛时候题面给的是5000

然后先从s来遍历所有点&＃xff0c;如果邻接信息里面含有s到i的边&＃xff0c;那么将i插入到set里面&＃xff0c;并将dis[i]置为-1&＃xff0c;如果不含有s到i的边&＃xff0c;就将i插入队列&＃xff0c;并将dis[i]置为1

然后依次访问队列里面的元素x&＃xff0c;遍历set&＃xff0c;如果set中的点y不具有一条x到y的边&＃xff0c;那么就将这个点标记&＃xff0c;取出set&＃xff0c;然后更新dis[y]

当set为空的时候直接return。

其实set可以用链表代替不过用set可以偷懒...

大概思路就是这样。然后就可以解决这题了。

代码&＃xff1a;

#include
#include