codeforces28B

题目链接：codeforces 28 B. pSort

题目大意：一个数列，初始顺序为S[i] = i;目标顺序为a[i] ;每个位置i的元素都可以和位置j的元素互换位置，当前仅当|i-j| = d[i]。问能否有初始数列到达目的数列

思路：乍一看，有点蒙。细想一下其实也不难。因为他只问每个数能否到达目的位置，也就是说有没有一条路是的S[i] 和a[i] 连通起来。因为n很小，所以我们可以直接根据d数组进行建图。然后用最短路思想看是否连通。。然后依次判断即可。

这里有两个点需要特别注意 ：i -> i 肯定是可以到达的，所以初始化为1

若1 -> 2 可达，3 -> 2 可达，则1 - > 3 可达。。所以在求是否连通时需要双重代换load[i][j] |= ((load[i][k] & load[j][k]) | (load[i][k] & load[k][j]));

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>

using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")
#define maxn 205
#define MOD 1000000007
#define mem(a , b) memset(a , b , sizeof(a))
#define LL long long
#define ULL unsigned long long
const long long INF=0x3fffffff;
int n , m;
int a[maxn] , d[maxn];
int load[maxn][maxn];

int main()
{
    while(scanf("%d" , &n) != EOF)
    {
        mem(load , 0);
        for(int i = 1 ; i <= n ; i ++ )
            scanf("%d" , &a[i]);
        for(int i = 1 ; i <= n ; i ++ )
            scanf("%d" , &d[i]);
        for(int i = 1 ; i <= n ; i ++)
        {
            load[i][i] = 1;
            int tmp = d[i];
            int down =  i - d[i];
            if(down >= 1 && down <= n) load[i][down] = 1;
            down = i + d[i];
            if(down >= 1 && down <= n) load[i][down] = 1;
        }
        int flag = 0;
        for(int k = 1 ; k <= n ; k ++)
        {
            for(int i = 1 ; i <= n ; i ++)
            {
                for(int j = 1 ; j <= n ;j ++)
                {
                    load[i][j] |= ((load[i][k] & load[j][k]) | (load[i][k] & load[k][j]));
                   // gra[i][j]|=(gra[i][k]&gra[j][k])|(gra[i][k]&gra[k][j]);
                }
            }
        }
        for(int i = 1 ; i <= n ; i ++)
        {
            if(!load[i][a[i]])
            {
                flag = 1;
                break;
            }
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

codeforces28B

原文：http://blog.csdn.net/qq_24477135/article/details/51355570