[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;
}

加入对话

6条评论

  1. 回复见习YY:首先很容易理解一种 nm lg K的做法,就是二分答案,加多一条边做限制为 d[S]-d[T]>=ans (S,T分别对应最低楼和最高楼的先后顺序根据输入顺序调一下)。如果无解,那么缩小答案,否则增大答案。对吧?然后现在你围观到最短路的本质,d[S]->d[T]的最短路径已经求出来了。那么如果加小于d[S]->d[T]的边,那么必定构成负权环,最大能加的,就是d[S]->d[T]这个路径的长度。

留下评论

回复 见习YY 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注