最少需要多少辆巴士才能让所有乘客到达 1 号站

Question

给定一个拥有 N 个公交车站和 N-1 条道路的城市。所有城市公交车站均可通过连接道路到达。站点的值可以是 0 或 1。0 表示该站点没有乘客，1 表示该站点有乘客。

找出使所有乘客都能到达车站 1 所需的最少巴士数量。

一辆巴士不能两次到达同一个站点，并且每辆巴士都有无限的载客量。

我的方法目前获取在某个时刻遇到乘客的叶节点的数量。然而，我的解决方案在这种情况下会重复计算，如下所示：

给定这 2 条可能的路径：1- 2 - 3 和 1- 2- 4，并且节点 2 处只有一名乘客。我的解决方案将两条路径都视为有效。

void dfs(int curr, int parent, bool passInPath, int *resPointer, unordered_map<int, vector<int> > &adjmap, int passengers[])
{
    bool leaf = true;
    bool passenger = false;
    if (passInPath || passengers[curr])
    {
        passenger = true;
    }
    for (auto neigh : adjmap[curr])
    {
        if (neigh != parent && neigh != 1)
        {
            dfs(neigh, curr, passenger, resPointer, adjmap, passengers);
            leaf = false;
        }
    }
    if (leaf && passenger)
    {
        *resPointer = *resPointer + 1;
    }
   
}

int minBuses(int N, int passengers[], int edges[][2])
{

    // first make adjacency list
    unordered_map<int, vector<int> > adjmap;
    for (int i = 0; i < N-1; i++)
    {
        int e1 = edges[i][0];
        int e2 = edges[i][1];
        adjmap[e1].push_back(e2);
        adjmap[e2].push_back(e1);
    }

    // result pointer
    int res = 0;
    int *resP = &res;

    // start from node 1 and iterate through all its neighbouts and launch dfs
    for (auto neigh : adjmap[1])
    {
        dfs(neigh, 1, false, resP, adjmap, passengers);
    }

    return res;
}

Answer 1

以下是一种可行的算法的概述：

procedure count_buses(node):
  sum = 0
  for child in node.children:
     sum += count_buses(child)
  sum = max (sum, node.has_passengers)
  return sum