本文涉及知识点

回溯 图论 深度优先
图论知识汇总

LeetCode 2065. 最大化一张图中的路径价值

给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。
合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。
请你返回一条合法路径的 最大 价值。
注意：每个节点 至多 有 四条 边与之相连。
示例 1：

输入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
输出：75
解释：
一条可能的路径为：0 -> 1 -> 0 -> 3 -> 0 。总花费时间为 10 + 10 + 10 + 10 = 40 <= 49 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 0 + 32 + 43 = 75 。
示例 2：

输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
输出：25
解释：
一条可能的路径为：0 -> 3 -> 0 。总花费时间为 10 + 10 = 20 <= 30 。
访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。
示例 3：

输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
输出：7
解释：
一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。
示例 4：

输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10
输出：0
解释：
唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ，最大路径价值为 0 。

提示：

n == values.length
1 <= n <= 1000
0 <= values[i] <= 108
0 <= edges.length <= 2000
edges[j].length == 3
0 <= uj < vj <= n - 1
10 <= timej, maxTime <= 100
[uj, vj] 所有节点对 互不相同 。
每个节点 至多有四条 边。
图可能不连通。

回溯

10 <= timej, maxTime <= 100，所以最多经过10条边。每个节点最多4条边。意味着：
回溯层次最多10层，每种状态最多四种子状态。
层次结束：当前用时大于maxTime。
需要处理状态：当前路径最终节点是0。
子状态：当前路径+最终节点的任意邻接点。
状态： 当前路径(vPath)，当前用时，当前价值(最大10⁹,int范围内)。
修改状态： vPath增加next
恢复状态：vPath Pop_back。
初始状态： vPath={0} 当前用时0 当前价值 values[0]
时间复杂度： O(4¹⁰10) $\approx$ 10⁷ 能过，但没有多少冗余。
O(10)是std::find。 可以用空间换时间vUseCnt记录各节点在路径出现的次数，这样时间复杂度可以降到O(4¹⁰)

回溯代码

核心代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class Solution {
public:
	int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
		vector<int> vPath = { 0 };
		auto neiBo = CNeiBo::Three(values.size(),edges, false);
		int iRet = 0;
		std::function<void(int, int)> BackTrack = [&](int iTime, int value) {
			if (iTime > maxTime) { return; }
			if (0 == vPath.back()) { iRet = max(iRet, value); }
			for (const auto& [next,time] : neiBo[vPath.back()]) {
				auto it = std::find(vPath.begin(), vPath.end(), next);
				const int iNewValue = ((vPath.end() == it) ? values[next] : 0) + value;
				vPath.emplace_back(next);				
				BackTrack(iTime + time, iNewValue);
				vPath.pop_back();
			}
		};
		BackTrack(0, values[0]);
		return iRet;
	}
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	vector<int> values;
	vector<vector<int>> edges;
	int maxTime;
	{
		Solution slu;
		values = { 5,10,15,20 }, edges = { {0,1,10},{1,2,10},{0,3,10} }, maxTime = 30;
		auto res = slu.maximalPathQuality(values, edges, maxTime);
		Assert(25, res);
	}
	{
		Solution slu;
		values = { 0,32,10,43 }, edges = { {0,1,10},{1,2,15},{0,3,10} }, maxTime = 49;
		auto res = slu.maximalPathQuality(values, edges, maxTime);
		Assert(75, res);
	}
	
	{
		Solution slu;
		values = { 1,2,3,4 }, edges = { {0,1,10},{1,2,11},{2,3,12},{1,3,13} }, maxTime = 50;
		auto res = slu.maximalPathQuality(values, edges, maxTime);
		Assert(7, res);
	}
	{
		Solution slu;
		values = { 0,1,2 }, edges = { {1,2,10} }, maxTime = 10;
		auto res = slu.maximalPathQuality(values, edges, maxTime);
		Assert(0, res);
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51

2023年4月

class Solution {
public:
int maximalPathQuality(vector& values, vector& edges, int maxTime) {
m_vValues = values;
m_iMaxTime = maxTime;
m_vNeiB.resize(values.size());
for (const auto& v : edges)
{
m_vNeiB[v[0]].emplace_back(v[1], v[2]);
m_vNeiB[v[1]].emplace_back(v[0], v[2]);
}
std::unordered_multiset mVisit;
dfs(0, -1, 0, 0, mVisit);
return m_iMaxScore;
}
void dfs(int iCur, int iParent, int iScore, int iTime, std::unordered_multiset& mVisit)
{
if (iTime > m_iMaxTime)
{
return;
}
if (!mVisit.count(iCur))
{
iScore += m_vValues[iCur];
}
if (0 == iCur)
{
m_iMaxScore = max(m_iMaxScore, iScore);
}
mVisit.emplace(iCur);
for (const auto& it : m_vNeiB[iCur])
{
dfs(it.first, iCur, iScore, iTime + it.second, mVisit);
}
mVisit.erase(mVisit.find(iCur));
}
int m_iMaxScore;
int m_iMaxTime;
vector m_vValues;
vector < vector>> m_vNeiB;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。