0
0

【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

本文涉及知识点

树上倍增 内向基环树 图论

LeetCode2836. 在传球游戏中最大化函数值

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。
总共有 n 名玩家，玩家 编号 互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。
你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。
如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + … + receiver(k)[x] 。
你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。
请你返回函数的 最大值 。
注意：receiver 可能含有重复元素。
示例 1：

传递次数 传球者编号 接球者编号 x + 所有接球者编号
2
1 2 1 3
2 1 0 3
3 0 2 5
4 2 1 6

输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。
示例 2：

传递次数 传球者编号 接球者编号 x + 所有接球者编号
4
1 4 3 7
2 3 2 9
3 2 1 10

输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示：

1 <= receiver.length == n <= 105
0 <= receiver[i] <= n - 1
1 <= k <= 1010

树上倍增

记录各节点传球一次的接受者和积分。
然后计算传球两次的接受者和积分。

     ⋯ 
    
   
  
    \cdots 
   
  
⋯ 4 次  
 
  
   
   
     ⋯ 
    
   
  
    \cdots 
   
  
⋯

 
  
   
   
     ⋯ 
    
   
  
    \cdots 
   
  
⋯ 8 次  
 
  
   
   
     ⋯ 
    
   
  
    \cdots 
   
  
⋯

 
  
   
    
    
      ⋮ 
     
     
      
     
    
   
  
    \vdots 
   
  
⋮

代码

核心代码

classCPow2{public:CPow2(vector<int>& receiver,longlong k):m_c(receiver.size()){longlong tmp = k;int iPow2 =0;for(; iPow2 <=63;iPow2++){if((1LL<< iPow2)== tmp){break;}
            tmp &=~(1LL<< iPow2);}
        m_vParent.assign(iPow2 +1,vector<int>(m_c));
        m_vSum.assign(iPow2 +1,vector<longlong>(m_c));for(int i =0; i < m_c; i++){
            m_vParent[0][i]= receiver[i];
            m_vSum[0][i]=  receiver[i];}for(int j =1; j <= iPow2; j++){for(int i =0; i < m_c; i++){constint next = m_vParent[j -1][i];
                m_vParent[j][i]= m_vParent[j -1][next];
                m_vSum[j][i]= m_vSum[j-1][i]+ m_vSum[j-1][next];}}}longlongQuery(int cur,longlong k){longlong ans =0;for(int i =0; i < m_vParent.size(); i++){if((1LL<< i)& k){
                ans += m_vSum[i][cur];
                cur = m_vParent[i][cur];}}return ans;}constint m_c;protected:    
    vector<vector<int>> m_vParent;
    vector<vector<longlong>> m_vSum;};classSolution{public:longlonggetMaxFunctionValue(vector<int>& receiver,longlong k){
        CPow2 pow(receiver, k);longlong llMax =0;for(int i =0; i < pow.m_c; i++){
            llMax =max(llMax, i+pow.Query(i, k));}return llMax;}};

测试用例

template<classT,classT2>voidAssert(const T& t1,const T2& t2){assert(t1 == t2);}template<classT>voidAssert(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]);}}intmain(){
    vector<int> receiver;longlong k;{
        Solution sln;
        receiver ={1,0}, k =10000000000;auto res = sln.getMaxFunctionValue(receiver, k);Assert(5000000001, res);}{
        Solution sln;
        receiver ={2,0,1}, k =4;auto res = sln.getMaxFunctionValue(receiver, k);Assert(6, res);}{
        Solution sln;
        receiver ={1,1,1,2,3}, k =3;auto res = sln.getMaxFunctionValue(receiver, k);Assert(10, res);}}

2023年8月

class CCycle
{
public:
CCycle(vector& receiver):m_receiver(receiver),m_c(receiver.size())
{
}
void Init(const unordered_set& setNotCycle)
{
CalCycleDis(setNotCycle);
CalCycleNode();
}
long long CalScore(int begin, long long needNode)
{
const int iCycleHead = m_mNodeToCycleHead[begin];
const long long llCycleNum = needNode / m_mCycleNodes[iCycleHead].size();//需要走多少整圈
needNode %= m_mCycleNodes[iCycleHead].size();//不足一圈部分
const long long llCycleScore = m_vDisScoreToCycelHead[m_receiver[iCycleHead]].second;//完整一圈的分数
if (0 == needNode)
{
return llCycleScore * llCycleNum;
}
const int iNodeNumToHead = m_vDisScoreToCycelHead[begin].first+1;//当前点到环首,共经过多少个点
long long llRet = m_vDisScoreToCycelHead[begin].second;
if (needNode > iNodeNumToHead )
{//过了环首后，还需要继续
const int iSubBegin = m_mCycleNodes[iCycleHead][needNode - iNodeNumToHead+1];
llRet += llCycleScore - m_vDisScoreToCycelHead[iSubBegin].second ;
}
else if( needNode < iNodeNumToHead)
{//没到环首
const int index = (m_mCycleNodes[iCycleHead].size() - (iNodeNumToHead - needNode - 1)) % m_mCycleNodes[iCycleHead].size();
const int iSubBegin = m_mCycleNodes[iCycleHead][index];
llRet -= m_vDisScoreToCycelHead[iSubBegin].second;
}
return llRet + llCycleScore* llCycleNum;
}
protected:
void CalCycleNode()
{
for (const auto& head : m_setCycelHead)
{
m_mCycleNodes[head].emplace_back(head);
m_mNodeToCycleHead[head] = head;
for (auto next = m_receiver[head]; next != head; next = m_receiver[next])
{
m_mCycleNodes[head].emplace_back(next);
m_mNodeToCycleHead[next] = head;
}
}
}
void CalCycleDis(const unordered_set& setNotCycle)
{
//环上各点到环首（编号最小的点)的距离
m_vDisScoreToCycelHead.assign(m_c, std::make_pair(-1, -1));
for (int i = 0; i < m_c; i++)
{
if (setNotCycle.count(i))
{
continue;//非环
}
DFSHead(i, i);
}
}
std::pair<int, long long> DFSHead(int cur, int head)
{
if (-1 != m_vDisScoreToCycelHead[cur].first)
{
return m_vDisScoreToCycelHead[cur];
}
if (cur == head)
{
m_setCycelHead.emplace(head);
m_vDisScoreToCycelHead[cur] = std::make_pair(0, cur);
DFSHead(m_receiver[cur], head);
return m_vDisScoreToCycelHead[cur];
}
const auto [nextDis, nextScore] = DFSHead(m_receiver[cur], head);
return m_vDisScoreToCycelHead[cur] = std::make_pair(nextDis + 1, nextScore + cur);
}
vector<std::pair<int, long long>> m_vDisScoreToCycelHead;//环上个点到环首（编号最小): 距离 和 分数(包括当前点、环首)
unordered_set m_setCycelHead;//环首
unordered_map<int, vector> m_mCycleNodes;//环上各点(按顺序存储)
unordered_map<int, int> m_mNodeToCycleHead;//各点对应环首
const int m_c;
const vector& m_receiver;
};

class Solution {
public:
long long getMaxFunctionValue(vector& receiver, long long k) {
m_c = receiver.size();
m_receiver = receiver;
k++;//点数比边数多1
//由于出度为1,所以没个联通区域只有一个环
//由于点数等于边数，故每个联通区域必定有一个环
//由于出度为1,所以进入环后，就只能在环上循环
//计算入度
vector vInDeg(m_c);
for (const auto& n : receiver)
{
vInDeg[n]++;
}
queue que;
for (int i = 0; i < m_c; i++)
{
if (0 == vInDeg[i])
{
m_setInDeg0.emplace(i);
que.emplace(i);
}
}
//通过拓扑排序判断那些点时环上
while (que.size()) {
const int cur = que.front();
que.pop();
m_setNotCycle.emplace(cur);
const int next = receiver[cur];
vInDeg[next]–;
if (0 == vInDeg[next])
{
que.emplace(next);
}
}

    //求各点到环上的次数，及距离
    m_vDisScoreToCycle.assign(m_c, std::make_tuple(- 1,-1,-1));
    for (int i = 0; i < m_c; i++)
    {
        dfs(i);
    }

    m_vRet.assign(m_c,-1);
    CCycle cycle(receiver);
    cycle.Init(m_setNotCycle);
    //处理整个路径都在环上
    for (int i = 0; i < m_c; i++)
    {
        if (m_setNotCycle.count(i))
        {
            continue;
        }        
        m_vRet[i] = cycle.CalScore(i, k);
    }
    //处理整个路径不在环上的点
    for (const auto cur : m_setInDeg0)
    {
        dfsLen(cur, k);
    }
    //非环开始，环结束
    for (int i = 0; i < m_c; i++)
    {
        if (-1 != m_vRet[i])
        {
            continue;
        }
        m_vRet[i] = get<1>(m_vDisScoreToCycle[i]) + cycle.CalScore(get<2>(m_vDisScoreToCycle[i]), k - get<0>(m_vDisScoreToCycle[i]));
    }
    return *std::max_element(m_vRet.begin(),m_vRet.end());
}
void dfsLen(int cur, const long long llNeedNode)
{    
    if (get<0>(m_vDisScoreToCycle[cur]) < llNeedNode)
    {
        return ;
    }
    long llScoer = 0;
    int r = cur;
    for(int i = 0 ; i < llNeedNode;i++ )
    {
        llScoer += r;
        r = m_receiver[r];
    }
    m_vRet[cur] = llScoer;
    while (get<0>(m_vDisScoreToCycle[m_receiver[cur]]) >= llNeedNode)
    {
        llScoer += r - cur;
        cur= m_receiver[cur];
        r = m_receiver[r];
        m_vRet[cur] = llScoer;
    }        
}
std::tuple<int,long long,int> dfs(int cur)
{
    auto& curRes = m_vDisScoreToCycle[cur];
    if (-1 != get<0>(curRes))
    {
        return curRes;
    }
    if (!m_setNotCycle.count(cur))
    {
        return curRes = std::make_tuple(0,0,cur);
    }    
    auto [iDis,iScore,iCycle] = dfs(m_receiver[cur]);
    return curRes = std::make_tuple(iDis+1,iScore+cur, iCycle);
}        
std::unordered_set<int> m_setNotCycle,m_setInDeg0;//非环上点； 入度为0的点
vector<tuple<int,long long,int>> m_vDisScoreToCycle;
std::unordered_map<int, int> m_mNodeToCycle;
vector<long long> m_vRet;
int  m_c;
vector<int> m_receiver;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

标签： 图论 算法 c++
本文转载自: https://blog.csdn.net/he_zhidan/article/details/136948853
版权归原作者 闻缺陷则喜何志丹 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航