题目描述

有 n 个小朋友，编号 1∼n。

每个小朋友都拿着一个号码牌，初始时，每个小朋友拿的号码牌上的号码都等于其编号。

每个小朋友都有一个幸运数字，第 i 个小朋友的幸运数字为 di。

对于第 i 个小朋友，他可以向第 j 个小朋友发起交换号码牌的请求，当且仅当 |i−j|=di 成立。

注意，请求一旦发出，对方无法拒绝，只能立刻进行交换。

每个小朋友都可以在任意时刻发起任意多次交换请求。

给定一个 1∼n 的排列 a1,a2,…,an。

请问，通过小朋友相互之间交换号码牌，能否使得第 i 个小朋友拿的号码牌上的号码恰好为 ai，对 i∈[1,n] 均成立。

输入格式
第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 n 个整数 d1,d2,…,dn。

输出格式
共一行，如果能做到，则输出 YES，否则输出 NO。

数据范围
前 6 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤100，1≤di≤n，保证 a1∼an 是一个 1∼n 的排列。

样例

输入样例1：
5
5 4 3 2 1
1 1 1 1 1
输出样例1：
YES
输入样例2：
7
4 3 5 1 2 7 6
4 6 6 1 6 6 1
输出样例2：
NO
输入样例3：
7
4 2 5 1 3 7 6
4 6 6 1 6 6 1
输出样例3：
YES

图的连通性，如果自己能通过别人找到自己要的那个人，这个人就通过。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
bool b[111];
int n,a[111],d[111],mp[111][111];
bool bfs(int st,int ed){
    queue<int>p;
    memset(b, 0, sizeof(b));
    b[st]=1;
    p.push(st);
    while(p.size()){
        int x=p.front();
        if(x==ed)return true;
        p.pop();
        for (int i = 1; i <= n; i ++ ){
            if(mp[x][i]==1&&b[i]==0){
                b[i]=1;
                p.push(i);
            }
        }
    }
    return false;
}
int main()
{
    cin >> n ;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++ ){
        cin>>d[i];
        int x=i-d[i];
        if(x>0){
            mp[i][x]=1;
            mp[x][i]=1;
        }
        x=i+d[i];
        if(x<=n){
            mp[i][x]=1;
            mp[x][i]=1;
        }
    }

    for (int i = 1; i <= n; i ++ ){
        if(!bfs(i,a[i])){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}