2010 ACM-ICPC Multi-University Training Contest（1）——Host by FZU

题目大意：在一条直线上有N个房子，每个房子的高度不一样，一个超人可以将这N个房子

左右移动，但是不能改变房子的相对位置。位置都为整数点。同一位置不能有两个以上的房

子两个超人从最矮的房子开始，跳到刚好比他所在房子高的房子上去，一直这样跳，每次跳

到的房子都比现在所在的房子高，而且每次跳的水平距离不能超过D米。问：如何将这些房

子进行合理的摆放(不改变相对位置的前提下)，使得超人能够经过所有的房子跳到最高的房

子，又要使最矮的房子和最高的房子之间的距离最远?

输入说明：

第一行：先输入一个T，表示T组数据。

每组第一行：输入N D，表示N个房子，每次最多水平跳D米。

接下来N个数：表示从左到右N个房子的高度，输入顺序表示了房子的相对位置。

思路：差分约束系统。把这道题目分解来看。可以分解为两个条件。

第1条：两个房子之间水平距离至少为1(即不能再同一位置上)

第2条：超人每次最多跳D米

现将房子的高度和代表相对位置的序号存入结构体中，用结构体数组arr[]表示。

因为房子之间的水平距离至少为1，将条件转换为：arr[i].No - arr[i+1].No <= -1，

将边存入差分约束系统表示的图中。然后对结构体按房子高度从低到高排序，这样结

构体中房子的顺序就变为超人跳房子的顺序，因为超人每次最多水平跳D米，将条件

转化为：arr[i+1].No - arr[i].No <= D，将边存入差分约束系统表示的图中，然后源

点s为arr[1].No，终点t为arr[N].No，用SPFA来判断是否符合条件，符合输出Dist[t]，

不符合输出"-1"。

注意：此题最主要是建边的时候，判断两者起点和终点的序号大小，让大的序号指向

小的序号。还有INF要设置的大一些。试了几次，发现0xfffffff不行，0x7fffffff就可以

了。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x7fffffff; //之前定义0xfffffff错误。
using namespace std;
const int MAXN = 1100;
const int MAXM = MAXN*MAXN;

struct EdgeNode
{
    int to;
    int w;
    int next;
}Edges[MAXM];

struct House
{
    int Hight;  //房子高度
    int No;     //房子序号
}arr[MAXN];

bool cmp(House a, House b)
{
    return a.Hight < b.Hight;
}
int Head[MAXN],Dist[MAXN],vis[MAXN],outque[MAXN],id;

void AddEdges(int u,int v,int w)
{
    Edges[id].to = v;
    Edges[id].w = w;
    Edges[id].next = Head[u];
    Head[u] = id++;
}
int SPFA(int s, int t,int N)
{
    memset(vis,0,sizeof(vis));
    memset(outque,0,sizeof(outque));
    for(int i = 0; i <= N; ++i)
        Dist[i] = INF;
    Dist[s] = 0;
    vis[s] = 1;
    queue<int> Q;
    Q.push(s);
    while( !Q.empty() )
    {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        outque[u]++;
        if(outque[u] > N)
            return -1;
        for(int i = Head[u]; i != -1; i = Edges[i].next)
        {
            int temp = Dist[u] + Edges[i].w;
            if(temp < Dist[Edges[i].to])
            {
                Dist[Edges[i].to] = temp;
                if( !vis[Edges[i].to])
                {
                    vis[Edges[i].to] = 1;
                    Q.push(Edges[i].to);
                }
            }
        }
    }
    return Dist[t];
}

int main()
{
    int T,N,D,kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        memset(Head,-1,sizeof(Head));
        scanf("%d%d", &N, &D);
        id = 0;
        for(int i = 1; i <= N; ++i)
        {
            scanf("%d", &arr[i].Hight);
            arr[i].No = i;
            if(i != N)
                AddEdges(i+1,i,-1);
        }

        sort(arr+1,arr+N+1,cmp);
        for(int i = 1; i < N; ++i)
        {
            int u = arr[i].No;
            int v = arr[i+1].No;
            if(u > v)
                swap(u,v);
            AddEdges(u,v,D);
        }
        int u = arr[1].No;
        int v = arr[N].No;
        if(u > v)
            swap(u,v);
        printf("Case %d: %d\n",++kase,SPFA(u,v,N));
    }

    return 0;
}

HDU3440 House Man【SPFA】【差分约束】