[JZOJ 100026] [NOIP2017提高A组模拟7.7] 图 解题报告 （倍增）

题目链接：

http://172.16.0.132/senior/#main/show/100026

题目：

有一个$n$个点$n$条边的有向图，每条边为$<i,f(i),w(i)>$，意思是$i$指向$f(i)$的边权为$w(i)$的边，现在小A想知道，对于每个点的$s_i$和$m_i$。
$s_i$:由$i$出发经过$k$条边，这$k$条边的权值和。
$m_i$:由$i$出发经过$k$条边，这$k$条边的权值最小值。

题解：

倍增即可（倍增的套路，转移是唯一的，体现在本题中是每个点出度为1）

$to[i][k]$表示节点i经过$2^k$个节点到达哪个节点，转移$to[i][k]=to[to[i][k-1]][k-1]$，边权和和路径最小值同理

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=1e5+;

const int M=;

const int inf=1e9;

int n;

ll k;

int to[N][M],mi[N][M];

ll sum[N][M];

inline ll read()

{

    char ch=getchar();

    ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int main()

{

    n=read();k=read();

    for (int i=;i<n;i++) to[i][]=read();

    for (int i=;i<n;i++) {sum[i][]=read();mi[i][]=sum[i][];}

    for (int i=;i<M;i++)

    {

        for (int j=;j<n;j++) to[j][i]=to[to[j][i-]][i-];

        for (int j=;j<n;j++)

        {

            sum[j][i]=sum[j][i-]+sum[to[j][i-]][i-];

            mi[j][i]=min(mi[j][i-],mi[to[j][i-]][i-]);

        }

    }

    for (int i=;i<n;i++)

    {

        ll s=,kk=k;

        int m=inf,p=i;

        for (int j=M-;j>=;j--)

        {

            if (!kk) break;

            if ((1ll<<j)<=kk)

            {

                kk-=1ll<<j;

                s+=sum[p][j];

                m=min(m,mi[p][j]);

                p=to[p][j];

            }

        }

        printf("%lld %d\n",s,m);

    }

    return ;

}

[JZOJ 100026] [NOIP2017提高A组模拟7.7] 图 解题报告 （倍增）的相关教程结束。