链接:
题意
一个无向无根树,每个点上有Coins[T]个金币,每次你可以选择吸收离自己距离小于等于2的节点的所有金币,也可以移动到相邻格子上,求全部吸完最小的移动次数(任选起点,但吸完要返回起点)
解:
由于计算的是移动次数,所以你可以认为一直在吸,走到哪儿吸到哪儿
计算最后移动次数很简单,由于要回到起点,所以移动次数一定是(n-1)*2-当n>0时,因为两个点之间要经过两次(来回且无环)
根据度,我们可以移除两次,度为0和1的节点,这些节点的特点是可以看做叶子节点,由于我们可以直接吸距离2的所有金币,所以我们在父节点不需要向下移动,就可以处理掉这些叶子结点。要注意的是,做这一步时,要等所有叶子结点都挑出来以后再更新度,以免提前计算将要成为叶子节点的节点
同时要记得先把所有没金币的叶子节点去掉,这边要注意和上面不同的是,即时更新度,要把新的叶子结点中没金币的也去掉(我偷懒了,大循环了)
实际代码:
#include
using namespace std;
int collectTheCoins(vector& coins, vector>& edges)
{
int lg=coins.size();
if(lg<=5) return 0;
vector>Map(lg);
vectorbook(lg);
//边结构
for(auto edge:edges)
{
//if(coins[edge[0]]==0 || coins[edge[1]]==0) continue;
Map[edge[0]].push_back(edge[1]);
Map[edge[1]].push_back(edge[0]);
}
while(true)
{
bool kill=0;
for(int j=0;jTrue;
for(int j=0;j
限制:
n == coins.length
1 <= n <= 3 * 104
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges
表示一棵合法的树。