Problem 1038 Function Graph（foj内网）（dp+倍增）

201707 （ACM）动态规划 （ACM）倍增

题解

• 倍增思想

代码

#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)a.size()
const int N=100005;
int n,k;
int a[N],b[N],f[N][40],Min[N][40];
ll sum[N][40];
int main() {
    while(~scanf("%d%d",&n,&k)) {
        ///init
        memset(sum,0,sizeof(sum));
        rep(i,0,N) rep(j,0,40) Min[i][j]=1e9;
        ///read
        rep(i,1,n+1) scanf("%d",a+i),f[i][0]=a[i]+1;
        rep(i,1,n+1) scanf("%d",b+i),sum[i][0]=Min[i][0]=b[i];
        ///solve
        int di=2;
        for(int i=1;di<=k;++i,di<<=1) {
            rep(j,1,n+1) {
                f[j][i]=f[f[j][i-1]][i-1];
            }
        }
        di=2;
        for(int i=1;di<=k;++i,di<<=1) {
            rep(j,1,n+1) {
                Min[j][i]=min(Min[j][i-1],Min[f[j][i-1]][i-1]);
                sum[j][i]=sum[j][i-1]+sum[f[j][i-1]][i-1];
            }
        }
        ///print
        rep(i,1,n+1) {
    //      cout<<"i="<<i<<endl;
            ll r1=0;
            int r2=1000000000;
            int u=i;
            for(int j=31;j>=0;--j) {
                if((k>>j)&1) {
                //  cout<<"j==="<<j<<endl;
                    r1=r1+sum[u][j];
                    r2=min(r2,Min[u][j]);
                    u=f[u][j];
                }
            }
            printf("%I64d %d\n",r1,r2);
        }
    }
    return 0;
}

Problem 1038 Function Graph
Accept: 2 Submit: 5
Time Limit: 1500 mSec Memory Limit : 65536 KB
Problem Description

给定一张有向的函数图，图中的每个点只有一条出边，每条边附有权值w(i)。

现在要求对于每个点来说，走k步经过的所有的边的权值和以及权值的最小值。
Input

多组测试数据，请处理到文件结束（EOF）。

每组测试数据的第一行为n,k(1 <= n <= 100000, 1 <= k <= 1000000000)，分别表示点的个数，以及步数。

第二行为序列f(0),f(1),...,f(n-1)，表示i->f(i)的有向边，0 <= f(i) <= n - 1。

第三行为序列w(0),w(1),...,w(n-1)，表示i->f(i)的权值，|w(i)| <= 1000000000。

点的编号为0到n-1。
Output

对于每组测试数据，输出n行，每行表示点i走k步的权值和以及权值最小值。
Sample Input
7 3
1 2 3 4 3 2 6
6 3 1 4 2 2 3
4 4
0 1 2 3
0 1 2 3
5 3
1 2 3 4 0
4 1 2 14 3
Sample Output
10 1
8 1
7 1
10 2
8 2
7 1
9 3
0 0
4 1
8 2
12 3
7 1
17 1
19 2
21 3
8 1
Hint

对于第一组测试据，点0走3步的路径为0->1->2->3，权值为6,3,1，权值和为10，最小值是1。
Source
2017暑期选拔赛第二场