在翻自己的图片库存的时候想到的……
给定一个有向图G=(V,E)G=(V,E)G=(V,E),你要选择一个点集SSS,使得∣S∣≤k,S⊆V|S|\le k,S\subseteq V∣S∣≤k,S⊆V
问max{min{dis(i,j):i∈S}:j∈V}\max\{\min\{dis(i,j):i\in S\}:j\in V\}max{min{dis(i,j):i∈S}:j∈V}的最小值
(其实就是多源最短路中最长的那一条要最短)
(如果iii不能到达jjj,那么有dis(i,j)=∞dis(i,j)=\inftydis(i,j)=∞)
原型是在一个有各种快捷方式的文件系统中找文件的过程
以下是一些可能的情况:
DAG