【题目大意】有n栋楼和一个SuperMan,每个都拥有一个唯一的高度,然后SuperMan每次会从第i高的楼,跳到第i+1高的楼上去。这些楼被安排在一个一维坐标轴上,然后这些楼有一个初始顺序,你是不能改变的。这些楼必须在整点上,并且不允许重叠,然后你要帮SuperMan安排这些楼,使得最高的楼和最低的楼距离之差最大。如果没有可行解,输出-1.
【算法分析】差分约束典型题目。根据那两个条件建好边,以最低楼和最高楼中顺序靠前的做起点,搞单源最短路,有环判无解,否则输出最高楼和最低楼d值之差的绝对值即可。
【其它】1Y
【CODE】
#include
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
}
void Bellman_Ford(){
int i,j;
for (i=1;i<=n;i++) d[i]=INF;
if (zz[1]
bool flag;
for (i=1;i<=n;i++){
flag=false;
for (j=1;j<=e;j++)
if (d[g[j].x]+g[j].w
d[g[j].y]=d[g[j].x]+g[j].w;
}
if (!flag) break;
}
if (flag) { puts("-1"); return; }
else if (zz[1]
}
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;
}
Orz
回复卡通BlueEye:Orz懂四边形不等式的LCC。。。Orz友情验题的LCC。。。
请教为什么这个最高楼和最低楼d值之差的绝对值一定是最大的距离差呢?
回复见习YY:首先很容易理解一种 nm lg K的做法,就是二分答案,加多一条边做限制为 d[S]-d[T]>=ans (S,T分别对应最低楼和最高楼的先后顺序根据输入顺序调一下)。如果无解,那么缩小答案,否则增大答案。对吧?然后现在你围观到最短路的本质,d[S]->d[T]的最短路径已经求出来了。那么如果加小于d[S]->d[T]的边,那么必定构成负权环,最大能加的,就是d[S]->d[T]这个路径的长度。
= =打错了,第二行那个式子应该是d[T]-d[S]>=ans
回复edward_mj:多谢神牛指点~一开始没仔细想最短路的性质