难度: Hard
Submission
运行时间: 200 ms
内存: 23.0 MB
class Solution:
def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:
if k>n-1:
return -1
g=[[] for _ in range(n)]
f=[[-1]*n for _ in range(1<<n)]
#已经到达过的城市状态，且目前所在城市
for u,v,c in highways:
g[u].append([v,c])
g[v].append([u,c])
for i in range(n):
f[1<<i][i]=0
res=-1
for s in range(1<<n):
for i in range(n):
if f[s][i]==-1:
continue
if s.bit_count()-1==k:
res=max(res,f[s][i])
for j,c in g[i]:
if s&(1<<j)==0:
ns=s|(1<<j)
f[ns][j]=max(f[ns][j],f[s][i]+c)
return res
Explain
该题解采用动态规划加状态压缩的方法来解决问题。首先，检查k是否大于n-1，如果是，则直接返回-1。接着，初始化城市间的连接关系以及状态转移表f。状态转移表f[s][i]代表到达城市集合s状态下，最后停留在城市i时的最大旅行费用。对于每个城市i，初始化f[1<<i][i]为0，表示起始于城市i的最小成本为0。然后，遍历所有可能的城市状态s，对每个状态，检查当前是否已经走过k条高速公路，并更新f[s][i]。如果已达k条公路，则尝试更新最大旅行费用结果res。最后，遍历所有可能的从城市i到城市j的路径，更新状态转移值。最终，返回最大的旅行费用。
时间复杂度: O(n^2 * 2^n)
空间复杂度: O(n * 2^n)
class Solution:
def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:
# 如果k大于n-1，则不可能有解
if k>n-1:
return -1
# 初始化城市连接关系
g=[[] for _ in range(n)]
# 初始化状态转移表
f=[[-1]*n for _ in range(1<<n)]
# 构建图
for u,v,c in highways:
g[u].append([v,c])
g[v].append([u,c])
# 初始化每个城市自身作为起点的状态
for i in range(n):
f[1<<i][i]=0
res=-1
# 遍历所有状态
for s in range(1<<n):
for i in range(n):
if f[s][i]==-1:
continue
# 如果当前已经走过k条高速公路
if s.bit_count()-1==k:
res=max(res,f[s][i])
# 遍历所有可能的下一步行动
for j,c in g[i]:
if s&(1<<j)==0:
ns=s|(1<<j)
f[ns][j]=max(f[ns][j],f[s][i]+c)
return res
Explore
在图论中，一个含有n个顶点的简单图的最大边数为n-1条，这是当且仅当该图为一棵树时的情况。若要经过k条高速公路，至少需要k个顶点，因此行走k条高速公路至少需要k+1个顶点，即n必须大于或等于k+1。如果k大于n-1，表示要求的高速公路数量超过了图中最多可能存在的边数，因此在这种情况下不可能找到一个满足条件的路径，所以算法直接返回-1。
`f[s][i]`中的`s`是一个整数，其二进制表示中的每一位代表一个城市是否被访问过，其中1表示已访问，0表示未访问。例如，如果有n个城市，`s`的二进制表示有n位，每位对应一个城市的访问状态。`i`代表当前所在的城市编号。因此，`f[s][i]`表示在访问了由`s`指定的城市集合后，最后停留在城市`i`时的最大旅行费用。这种表示方法允许我们在遍历时动态地存储和更新访问不同城市组合的最大费用。
`1<<i`是一个位操作，表示将数字1的二进制表示向左移动`i`位，结果是只有第`i`位是1，其他位都是0。这表示在状态`s`中，只有城市`i`被访问过，其他城市都未被访问。将`f[1<<i][i]`初始化为0意味着从城市`i`开始旅行，没有任何旅行成本，因为我们还没有离开起点。这是动态规划的基础情形，从每个城市自身出发的旅行成本为零。
在这个算法中，已经走过的高速公路数量是通过检查状态`s`的二进制表示中1的个数来确定的。每一位1表示访问了一个城市，而从一个城市到另一个城市需要经过一条高速公路。因此，如果已访问的城市数量为n，那么已经走过的高速公路数量为n-1（因为从第一个城市到第二个城市开始计数）。通过检查`bit_count()-1`等于k来判断是否已经走过k条高速公路。