[CF702E] Analysis of Pathes in Functional Graph - 倍增

Description

给定一个 \(n\) 个点的带权有向图，每个点有且仅有一条出边，对于每个点由它出发走 \(k\) 条边，求这 \(k\) 条边的权值和，以及最小值。

Solution

倍增

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define III IIIII
const int N = 100005;
const int M = 50;

int n,k,f[N][M],g[N][M],h[N][M],e[N],w[N];

int query_min(int p,int q)
{
    int ans=1e18;
    for(int i=0;i<M;i++)
    {
        if((q>>i)&1)
        {
            ans=min(ans, f[p][i]);
            p = h[p][i];
        }
    }
    return ans;
}

int query_sum(int p,int q)
{
    int ans=0;
    for(int i=0;i<M;i++)
    {
        if((q>>i)&1)
        {
            ans += g[p][i];
            p = h[p][i];
        }
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i];
        ++e[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        f[i][0]=w[i];
        g[i][0]=w[i];
        h[i][0]=e[i];
    }
    for(int j=1;j<M;j++)
    {
        for(int i=1;i<=n;i++)
        {
            f[i][j]=min(f[i][j-1],f[h[i][j-1]][j-1]);
            g[i][j]=g[i][j-1]+g[h[i][j-1]][j-1];
            h[i][j]=h[h[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=n;i++)
    {
        cout<<query_sum(i,k)<<" "<<query_min(i,k)<<endl;
    }
}

[CF702E] Analysis of Pathes in Functional Graph - 倍增

原文：https://www.cnblogs.com/mollnn/p/13586100.html