一个图论问题
查看原帖
一个图论问题
372299
超级玛丽王子楼主2021/2/21 19:08

RT,今天突发奇想想到的:

一个国家由首都城市和 nn 个普通城市组成,其中有些城市间可以修单向路,价格为其距离;有些城市间不能修路。现在给定首都城市和普通城市的坐标,请你求一种花费最小的修路方案,使得从首都城市出发能够到达任何一个普通城市,从任意普通城市出发也能够到达首都城市。

问题:

  1. 这个问题可解吗?
  2. 如果可解,大概用什么算法以及思路?复杂度?
2021/2/21 19:08
加载中...