【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和-阿里云开发者社区

涉及知识点

深度优先搜索图论树

LeetCode2646. 最小化旅行的价格总和

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的价格总和是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些非相邻节点并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1：

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]

输出：23

解释：

上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。

第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。

第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。

第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。

所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]

输出：1

解释：

上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。

第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。

所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

提示：

1 <= n <= 50

edges.length == n - 1

0 <= ai, bi <= n - 1

edges 表示一棵有效的树

price.length == n

price[i] 是一个偶数

1 <= price[i] <= 1000

1 <= trips.length <= 100

0 <= starti, endi <= n - 1

两次深度优先搜索

深度优先搜索计算进过各节点多少次

以任何一个节点（比如：0）为整课树的节点，有如下性质：

性质一：路径一定是：起点→ \rightarrow→ 公共祖先 → \rightarrow→ 终点特例是：起点或终点就是公共祖先。

性质二：如果某棵子树包括某次旅行的起点或终点，则此次旅行必定经过此子树根节点。如果起点和终点都是此子树的节点，也算。之后就不算了。

如何判断节点是否属于子树：

DFS 的开始，给节点编号（访问编号）m_vTime[cur]，从1到大。没有访问就是默认值0。

DFS结束时，访问编号大于等于m_vTime[cur]，是本子树的节点。

m_vNeedVis 记录各节点访问的需要访问的次数。

m_vHasDo 记录那些旅行的公共祖先已经访问。

深度优先搜索枚举半价

{ 子节点节点全价根节点半价 m i n ( 子节点节点全价，子节点节点半价 ) 根节点全价 \begin{cases} 子节点节点全价 & 根节点半价 \\ min(子节点节点全价，子节点节点半价) & 根节点全价 \\ \end{cases}{子节点节点全价min(子节点节点全价，子节点节点半价)根节点半价根节点全价

DFS2返回值两个：

一，全价、半价的较小值。

二，全价的最小值。

代码

核心代码

class CNeiBo2
{
public:
  CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
  {
    m_vNeiB.resize(n);
  }
  CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
  {
    m_vNeiB.resize(n);
    for (const auto& v : edges)
    {
      m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);
      if (!bDirect)
      {
        m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);
      }
    }
  }
  inline void Add(int iNode1, int iNode2)
  {
    iNode1 -= m_iBase;
    iNode2 -= m_iBase;
    m_vNeiB[iNode1].emplace_back(iNode2);
    if (!m_bDirect)
    {
      m_vNeiB[iNode2].emplace_back(iNode1);
    }
  }
  const int m_iN;
  const bool m_bDirect;
  const int m_iBase;
  vector<vector<int>> m_vNeiB;
};
class Solution {
public:
  int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
    CNeiBo2 neiBo(n, edges, false);
    m_vNeedVis.resize(n);
    m_vHasDo.resize(trips.size());
    m_vTime.resize(n);
    m_trips = trips;
    m_price = price;
    DFS(neiBo.m_vNeiB, 0, -1);
    return DFS2(neiBo.m_vNeiB, 0, -1).first;
  }
  void DFS(vector<vector<int>>& neiBo, int cur, int par)
  {
    m_vTime[cur] = ++m_llTime;
    for (const auto& next : neiBo[cur])
    {
      if (next == par)
      {
        continue;
      }
      DFS(neiBo, next, cur);
    }
    for (int i = m_trips.size()-1 ; i >=0 ; i--)
    {
      if (m_vHasDo[i])
      {
        continue;
      }
      const auto& v = m_trips[i];
      if ((m_vTime[v[0]] >= m_vTime[cur]) || (m_vTime[v[1]] >= m_vTime[cur]))
      {
        m_vNeedVis[cur]++;
        if ((m_vTime[v[0]] >= m_vTime[cur]) && (m_vTime[v[1]] >= m_vTime[cur]))
        { 
          m_vHasDo[i] = true;
        }
      }
    }
  }
  pair<int,int> DFS2(vector<vector<int>>& neiBo, int cur, int par)
  {
    int  i2 = m_price[cur]*m_vNeedVis[cur],i1 =i2/2;
    for (const auto& next : neiBo[cur])
    {
      if (next == par)
      {
        continue;
      }
      auto [i11,i21] = DFS2(neiBo, next, cur);
      i1 += i21;
      i2 += i11;
    }
    return make_pair(min(i1, i2), i2);
  }
  vector<int> m_vNeedVis,m_vTime;// 记录各节点访问的需要访问的次数。
  vector<bool>  m_vHasDo;// 记录那些旅行的公共祖先已经访问。
  int m_llTime = 0;
  vector<vector<int>> m_trips;
  vector<int> m_price;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
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]);
  }
}
int main()
{ 
  int n;
  vector<int>  price;
  vector<vector<int>> edges, trips;
  {
    Solution sln;
    n = 4, edges = { {0,1},{1,2},{1,3} }, price = { 2,2,10,6 }, trips = { {0,3},{2,1},{2,3} };
    auto res = sln.minimumTotalPrice(n, edges, price, trips);
    Assert(res,23);
  }
  {
    Solution sln;
    n = 2, edges = { {0,1} }, price = { 2,2 }, trips = { {0,0} };
    auto res = sln.minimumTotalPrice(n, edges, price, trips);
    Assert(res, 1);
  }
  {
    Solution sln;
    n = 5, edges = { {1,2},{2,0},{0,3},{3,4} }, price = { 12,26,22,12,2 };
    trips = { {3,3},{3,2},{3,0},{3,4},{1,1},{2,2},{4,0},{0,2},{2,3},{2,1},{4,2},{0,1},{4,2},{0,4},{0,3},{4,0},{4,0},{3,3},{4,3},{2,2},{4,2},{1,4},{3,2},{4,4},{4,2},{2,3},{4,3},{4,4},{4,2},{0,4},{4,2},{3,4},{4,0},{3,2},{3,1},{2,0},{0,4},{3,4},{2,0},{1,4},{4,2},{4,4},{2,1},{0,1},{4,1},{3,4},{0,4},{2,0},{2,0},{3,3},{4,4},{0,1},{0,1},{0,1},{2,0},{0,1},{3,1},{3,4},{3,4},{4,2},{0,4},{4,4},{3,2},{2,1},{3,2},{1,4},{1,0},{4,2},{4,3},{3,1},{4,4},{3,1},{1,0},{0,0},{0,0},{3,0},{0,2},{2,2},{3,3},{0,3} };;
    auto res = sln.minimumTotalPrice(n, edges, price, trips);
    Assert(res, 2037);
  }
  
}

2023年3月

class CNeiBo2

{

public:

CNeiBo2(int n, vector<vector>& edges, bool bDirect)

{

m_vNeiB.resize(n);

for (const auto& v : edges)

{

m_vNeiB[v[0]].emplace_back(v[1]);

if (!bDirect)

{

m_vNeiB[v[1]].emplace_back(v[0]);

}

vector<vector> m_vNeiB;

};

class Solution {

public:

int minimumTotalPrice(int n, vector<vector>& edges, vector& price, vector<vector>& trips) {

m_vParent.resize(n);

CNeiBo2 neBo(n, edges, false);

dfs(0, -1, neBo.m_vNeiB);

vector vTotalPrice(n);

for (const vector& trip : trips)

{

const auto& v0 = m_vParent[trip[0]];

const auto& v1 = m_vParent[trip[1]];

int i = 0;

for (; (i < min(v0.size(), v1.size())) && (v0[i] == v1[i]); i++);

vTotalPrice[v0[i - 1]] += price[v0[i - 1]];

for (int j = i; j < v0.size(); j++)

{

vTotalPrice[v0[j]] += price[v0[j]];

}

for (int j = i; j < v1.size(); j++)

{

vTotalPrice[v1[j]] += price[v1[j]];

}

int iRet = std::accumulate(vTotalPrice.begin(), vTotalPrice.end(), 0);

return iRet - MaxDFS(0, -1, neBo.m_vNeiB, vTotalPrice, true);

}

void dfs(int iCur, int iParent, const vector<vector>& vNeiBo)

{

if (-1 != iParent)

{

m_vParent[iCur] = m_vParent[iParent];

}

m_vParent[iCur].emplace_back(iCur);

for (const auto& next : vNeiBo[iCur])

{

if (iParent == next)

{

continue;

}

dfs(next, iCur, vNeiBo);

}

int MaxDFS(int iCur, int iParent, const vector<vector>& vNeiBo, const vector& vTotalPrice,bool bCanRoot)

{

int iRet = 0;

for (const auto& next : vNeiBo[iCur])

{

if (iParent == next)

{

continue;

}

iRet += MaxDFS(next, iCur, vNeiBo, vTotalPrice,true);

}

if ((!bCanRoot) || (0 == vTotalPrice[iCur]))

{

return iRet;

}

int iRet2 = vTotalPrice[iCur] / 2;

for (const auto& next : vNeiBo[iCur])

{

if (iParent == next)

{

continue;

}

iRet2 += MaxDFS(next, iCur, vNeiBo, vTotalPrice, false);

}

return max(iRet, iRet2);

}

vector<vector> m_vParent;

};

【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和

作者推荐

涉及知识点

LeetCode2646. 最小化旅行的价格总和

两次深度优先搜索

深度优先搜索计算进过各节点多少次

深度优先搜索枚举半价

代码

核心代码

测试用例

2023年3月

热门文章

最新文章

相关课程

相关电子书

相关实验场景