3.奢侈的河流旅行

题目描述

农夫约翰正带领着他的奶牛们去旅行。他们漂流在一个有N个港口的河流网络中，每个港口的标号分别是从1到N。开始的时候，他们在第一个港口，每个港口有且仅有两条可以开到其他港口的河流，并且河流的方向是单向的，船只能沿着河流的方向开。

在每一个港口，约翰可以选择向左边的河流或者向右边的河流开，约翰制定了一个长度为M的方向序列，序列中的字母或者是’L’或者是‘R’，‘L’表示向开向左边的港口，‘R’表示开向右边的港口。令人感觉奇怪的是，约翰执行这个长度为M的方向序列执行了K次。

问题描述：

请帮助约翰计算在执行了K次这种长度为M的序列之后，他最后在哪个港口。

输入

第一行三个整数，N，M和K。

接下来第2行到第N+1行，每行两个正整数，第i+1的两个整数表示第i个港口左边和右边的河流所去的其他港口的序号。

接下来一行，表示长度为M的方向序列，每个字母之间用空格隔开，字母只可能是‘L’或者‘R’。

输出

输出最后所在的港口的序号。

样例输入

样例输出

提示

数据范围：

1<=N<=1000,1<=M<=500,1<=K<=1000000000。

样例说明：

样例中，第一次序列执行完是在港口2（1-2-3-2），第二次序列执行完是在港口3（2-3-4-3），第三次序列执行完是在港口4（3-4-1-4）。所以最后的位置是在港口4。

说明：

注意这是一个有向图。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,j,x,i,net[900010],f[900010];
char ch[900010];
struct no{
   int l,r;
}a[900010];
main(){
   cin>>n>>m>>k;
   for(i=1;i<=n;i++)
       cin>>a[i].l>>a[i].r;
   for(i=1;i<=m;i++)cin>>ch[i];
   for(i=1;i<=n;i++){
       x=i;
       for(j=1;j<=m;j++)
           if(ch[j]=='L')x=a[x].l;
           else x=a[x].r;
       net[i]=x;
   }
   for(i=2;i<=n;i++)f[i]=-1;x=1;f[1]=0;
   for(i=1;i<=n+1;i++){
       x=net[x];
       if(f[x]<0)f[x]=i;
       else{k=k-f[x];i=i-f[x];break;}
   }
   k=k%i;
   for(i=1;i<=k;i++)x=net[x];
   cout<<x;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,j,x,i,net[900010],f[900010];
char ch[900010];
struct no{
    int l,r;
}a[900010];
main(){
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r;
    for(i=1;i<=m;i++)cin>>ch[i];
    for(i=1;i<=n;i++){
        x=i;
        for(j=1;j<=m;j++)
            if(ch[j]=='L')x=a[x].l;
            else x=a[x].r;
        net[i]=x;
    }
    for(i=2;i<=n;i++)f[i]=-1;x=1;f[1]=0;
    for(i=1;i<=n+1;i++){
        x=net[x];
        if(f[x]<0)f[x]=i;
        else{k=k-f[x];i=i-f[x];break;}
    }
    k=k%i;
    for(i=1;i<=k;i++)x=net[x];
    cout<<x;
}