[HDOJ3440 House Man]【差分约束系统】

【题目大意】有n栋楼和一个SuperMan，每个都拥有一个唯一的高度，然后SuperMan每次会从第i高的楼，跳到第i+1高的楼上去。这些楼被安排在一个一维坐标轴上，然后这些楼有一个初始顺序，你是不能改变的。这些楼必须在整点上，并且不允许重叠，然后你要帮SuperMan安排这些楼，使得最高的楼和最低的楼距离之差最大。如果没有可行解，输出-1.

【算法分析】差分约束典型题目。根据那两个条件建好边，以最低楼和最高楼中顺序靠前的做起点，搞单源最短路，有环判无解，否则输出最高楼和最低楼d值之差的绝对值即可。

【其它】1Y

【CODE】

#include const int N=1005;
const int E=500005;
const int INF=0x7FFFFFFF/2-22;
int n,e,D;
int d[N],a[N],zz[N];
struct edge{int x,y,w;}g[E];

int cmp(const void *A,const void *B){
    return a[*((int*)A)]-a[*((int*)B)];
}

void add(int x,int y,int w){
     g[++e].x=x; g[e].y=y; g[e].w=w;
}

void init(){
     int i;
     scanf("%d%d",&n,&D);
     for (i=1;i<=n;i++){
       scanf("%d",&a[i]); zz[i]=i; } qsort(zz+1,n,sizeof(int),cmp);
     e=0;
     for (i=1;i     for (i=1;i       if (zz[i]                     else add(zz[i+1],zz[i],D);
}

void Bellman_Ford(){
     int i,j;
     for (i=1;i<=n;i++) d[i]=INF;
     if (zz[1]                 else d[zz[n]]=0;
     bool flag;
     for (i=1;i<=n;i++){
         flag=false;
         for (j=1;j<=e;j++)
           if (d[g[j].x]+g[j].w             flag=true;
             d[g[j].y]=d[g[j].x]+g[j].w;
           }
         if (!flag) break;
     }
     if (flag) { puts("-1"); return; }
     else if (zz[1]                      else printf("%dn",d[zz[1]]-d[zz[n]]);
}

int main(){
    int i,Tc;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d: ",i);
        e=0;
        init();
        Bellman_Ford();
    }
    return 0;
}