House Man （HDU-3440） （差分限制-最短路模型+判負環）

In Fuzhou, there is a crazy super man. He can’t fly, but he could jump from housetop to housetop. Today he plans to use N houses to hone his house hopping skills. He will start at the shortest house and make N-1 jumps, with each jump taking him to a taller house than the one he is jumping from. When finished, he will have been on every house exactly once, traversing them in increasing order of height, and ending up on the tallest house.

The man can travel for at most a certain horizontal distance D in a single jump. To make this as much fun as possible, the crazy man want to maximize the distance between the positions of the shortest house and the tallest house.

The crazy super man have an ability—move houses. So he is going to move the houses subject to the following constraints:

1. All houses are to be moved along a one-dimensional path.

2. Houses must be moved at integer locations along the path, with no two houses at the same location.

3. Houses must be arranged so their moved ordering from left to right is the same as their ordering in the input. They must NOT be sorted by height, or reordered in any way. They must be kept in their stated order.

4. The super man can only jump so far, so every house must be moved close enough to the next taller house. Specifically, they must be no further than D apart on the ground (the difference in their heights doesn't matter).

Given N houses, in a specified order, each with a distinct integer height, help the super man figure out the maximum possible distance they can put between the shortest house and the tallest house, and be able to use the houses for training.

Input

In the first line there is an integer T, indicates the number of test cases.(T<=500)

Each test case begins with a line containing two integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤1000000). The next line contains N integer, giving the heights of the N houses, in the order that they should be moved. Within a test case, all heights will be unique.

Output

For each test case , output “Case %d: “first where d is the case number counted from one, then output a single integer representing the maximum distance between the shortest and tallest house, subject to the constraints above, or -1 if it is impossible to lay out the houses. Do not print any blank lines between answers.

Sample Input

3
4 4 
20 30 10 40 
5 6 
20 34 54 10 15 
4 2 
10 20 16 13 
           

Sample Output

Case 1: 3
Case 2: 3
Case 3: -1
           

題意：有n棟房子，給出每棟房子的高度和開始時的相對位置，可以移動一些房子，但不能改變這些房子的相對位置，現在從最矮的房子開始，每次跳至比它高的第一棟房子， 而且每次跳躍的水準距離最大是D，房子不能在同一位置，隻能在整點位置。問最矮的房子和最高的房子之間的最大距離可以是多少？如果不能從最矮的房子到達最高的房子則輸出-1。

思路：這道題的話，令dis[i]表示第i棟房子與第一棟房子之間的最大距離，那麼我們要求的就是的的dis[n],求最短路即可。首先每棟房子之間的相對位置已經确定且不能在同一位置，那麼dis[i+1] > dis[i],每次要跳至比它高的房子上，那麼我們需要對房子按高度排序。因為開始時已經規定标号小的點在标号大的點的左邊，這樣，我們如果從标号大的點到标号小的點，建一條這樣的邊就會有問題，隻能按小到大建邊，而且如果兩個排序後相鄰房子之間的标号大于D的話則不可能到最高的房子，因為房子不可能在同一位置，他們之間的距離至少是D。限制條件隻有這兩者，建邊時需要處理一下方向。最後如果最高的房子标号比矮的房子小的話，則以最高的房子為源點進行spfa，如果存在負環則輸出-1。

AC代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=10010;
const int inf=0x3f3f3f3f;
using namespace std;
struct  node
{
    int h;
    int id;
} a[maxx];
bool cmp(node x,node y)
{
    return x.h<y.h;
}
struct node
{
    int v;
    int w;
    int next;
} edge[maxx];
int head[maxx],dis[maxx],num[maxx];
bool vis[maxx];
int cnt,n,d;
void add(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int spfa(int u,int t)
{
    dis[u]=0;
    vis[u]=true;
    num[u]++;
    queue<int>q;
    q.push(u);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=false;
        for(int i=head[x]; i!=-1; i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(dis[v]>dis[x]+w)
            {
                dis[v]=dis[x]+w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                    if(++num[v]>n)
                        return -1;
                }
            }
        }
    }
    return dis[t];
}
void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    memset(num,0,sizeof(num));
}
int main()
{
    int t,k=0;
    scanf("%d",&t);
    while(t--)
    {
        k++;
        scanf("%d%d",&n,&d);
        init();
        for(int i=0; i<n; i++)
            a[i].id=i;
        for(int i=0; i<n; i++)
            scanf("%d",&a[i].h);
        sort(a,a+n,cmp);
        int flag=1;
        for(int i=0; i<n-1; i++)
        {
            if(flag)
            {
                add(i+1,i,-1);
                int u=min(a[i].id,a[i+1].id);
                int v=max(a[i].id,a[i+1].id);
                if (v-u>d)
                    flag=0;
                add(u,v,d);
            }
            else
                break;
        }
        int s=min(a[0].id,a[n-1].id);
        int e=max(a[0].id,a[n-1].id);
        if(flag)
            printf("Case %d: %d\n",k,spfa(s,e));
        else
            printf("Case %d: -1\n",k);
    }
    return 0;
}