hdu 3440 House Man(差分约束系统）

House Man

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2488    Accepted Submission(s): 1015

Problem Description 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
        

Author jyd  

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

题目链接

题意：要从高度最低的地方跳到高度最高的地方 每次跳跃的距离小于等于m 每次只能跳到下一个比他高但是和他高度最接近的位置 
每个位置都有一个高度值 并且顺序不能换 最低和最高的最远距离。

思路：差分约束系统

1.两个相邻点之间最小距离为一，则有d[i+1]-d[i]>=1,等价于  d[i]-d[i+1]<=-1;

2.高度最接近的两个点的最大距离为m,按距离排序之后可有     d[j+1]-d[j]<=m;

查分约束系统的条件找出来了；


剩下就是构图的事了。
由的d[i]-d[i+1]<=-1 的编辑条件可知，我们给各个点制定了一个方向，就是从左到右是依次增大的。
这就限定了的d[j+1]-d[j]<=m的连边条件，必须是由对应的序号小的点连向序号大的点，才对应了题目中的swap操作。

代码：
       
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
const int maxn=1010;
const int inf=1e9+7;
queue<int>q;
int dist[maxn],out[maxn],head[maxn],vis[maxn];
struct node
{
    int v,num;
    bool operator<(const node&p)const
    {
        return v<p.v;
    }
}a[maxn];
struct node2
{
    int to,next,v;
}edge[maxn*16];
int id=0;
void addedge(int u,int v,int d)
{
    edge[id].to=v;edge[id].v=d;
    edge[id].next=head[u];
    head[u]=id++;
}
void init(int n)
{
    while(!q.empty())
        q.pop();
    for(int i=0;i<=n;i++)
    {
        dist[i]=inf;
        out[i]=0;
        vis[i]=0;
    }
}
int spfa(int s,int t,int n)
{
    init(n);
    q.push(s);
    dist[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        if(++out[u]>n)return -1;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to,tmp=dist[u]+edge[i].v;
            if(tmp<dist[v])
            {
                dist[v]=tmp;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dist[t];
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        memset(head,-1,sizeof(head));
        id=0;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].v);
            a[i].num=i;
            if(i!=n)addedge(i+1,i,-1);
        }
        sort(a+1,a+n+1);
        for(int i=1;i<n;i++)
        {
            int u=a[i].num,v=a[i+1].num;
            if(u>v)
                swap(u,v);
            addedge(u,v,m);
        }
        int u=a[1].num,v=a[n].num;
        if(u>v)
            swap(u,v);
        printf("Case %d: %d\n",t,spfa(u,v,n));
    }
    return 0;
}