本文共 4041 字,大约阅读时间需要 13 分钟。
题目链接:
题目大意:
给一个
n n n 个点,
m m m 条边的无向简单带权连通图, 要求删边至最多剩余
k k k 条边.
定义"好点"是指删边后,
1 1 1 号节点到它的最短路长度仍然等于原图最短路长度的节点.
最大化删边后的好点个数
题目分析:
思路1:
用
d i j k s t r a dijkstra dijkstra 算法建出最短路径树,在树上跑
k k k 条边一定符合答案的最优性,因为每加一条树上的边就会多保留一个点,所以直接
b f s bfs bfs 跑一下就可以了
思路2:
因为要保证每加一条边尽可能的多一个点,而
d i j k s t r a dijkstra dijkstra 算法就是一个贪心的过程,所以可以累计
k k k 次松弛操作,这
k k k 条边一定是最优的
具体细节见代码:
思路一:最短路径树
#include #include #include #include #include #include #include #include #include
思路二: d i j k s t r a dijkstra dijkstra 算法+贪心
#include #include #include #include #include #include #include #include #include
转载地址:http://ghrxz.baihongyu.com/