【差分约束系统】 note
>>>>题目
【题目描述】
最近有一款很火的游戏,叫做八分音符酱,它和马里奥很相似,不过它的跳跃距离是由你的声音大小来控制
的。不过我们现在对玩法就行一些修改:
现有一共有n 个柱子,两个相邻的柱子之间的初始水平距离为1,蠢蠢的jyb 现在在最矮的柱子上,他每次
只能向恰好比这个柱子高的另一个柱子跳跃,最后要跳到最高的柱子上。
jyb 需要从第二个柱子跳到第一个柱子,再跳到第三个柱子。
jyb 的最大声音为d,代表他能在满足 |posi-posj| + |heighti-heightj | ≤d 的两个柱子之间跳跃。
假设我们可以在不改变它们位置的相对顺序的前提下水平移动柱子,调整他们的水平位置(但相邻间隔至少为1,且为整数)。
jyb 想问你:在能从最矮柱子跳到最高柱子的前提下,它们(最矮柱子跳到最高柱子) 的最大水平距离是多少。
【输入描述】
第1 行,1 个整数T, 表示数据组数,对于每组数据:
第1 行,1 个整数n;m,表示一共有多少个柱子。
接下来1 行,有n 个数,hi 表示柱子的高度。保证柱子高度互不相同
【输出描述】
对于每组数据,输出在能从最矮柱子跳到最高柱子的前提下,它们的最大水平距离是多少。如果不能,输出-1
【输入样例1】
2
3 4
3 2 4
3 4
3 2 6
【输出样例1】
2
-1
【输入样例2】
2
5 10
4 2 1 8 10
5 2
10 8 2 1 4
【输出样例】
12
-1
【数据范围及约定】
对于30% 的数据,1 n 100,1 d 1000,1 hi 1000;
•对于100% 的数据,1 T 100,1 n 103,1 d 106,1 hi 106。
>>>>分析
我们不能随意地将水平位置拉开,因为必须要能够从最矮的柱子跳到最高的柱子。
其实就相当于有了很多限制条件,显然这是一个差分约束系统。
先根据柱子的高度排序(初始化时用结构体记录高度和位置)
我们约定,在相邻两柱子,从下标小的向大的建边(以下用u(下标小),v(下标大)表示)
我们有两个约束条件:
1..根据题意:pos[v]-pos[u]+height[v]-height[u]≤d
2..两个相邻的柱子之间距离最少为1::pos[v]-pos[u]≥1
整理后得到
pos[v]-pos[u]≤d-(height[v]-height[u])
于是建边分为两种:
1.从i 到i+1建边,长度为 d-(height[v]-height[u])
2.从i+1到i建边,长度为-1
>>>>代码
#include<bits/stdc++.h> #define maxn 1005 using namespace std; struct node { int to,nxt,w; }e[maxn<<1]; struct node1 { int pos,h; }a[maxn]; int T,n,d,tot,flag,st,ed; int dis[maxn],head[maxn],in[maxn]; bool vis[maxn]; queue<int> q; bool cmp(const node1 &x,const node1 &y) { return x.h<y.h; } void add(int u,int v,int w) { e[++tot].to=v; e[tot].nxt=head[u]; e[tot].w=w; head[u]=tot; } int spfa(int st,int ed)//找最短路 { memset(dis,65,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); q.push(st),vis[st]=1; in[st]++,dis[st]=0; while(!q.empty()) { int now=q.front(); q.pop(),vis[now]=0; for(int i=head[now];i;i=e[i].nxt) { int v=e[i].to; if(dis[v]>dis[now]+e[i].w) { dis[v]=dis[now]+e[i].w; if(!vis[v]) { vis[v]=1; q.push(v); in[v]++; if(in[v]>=n+2) return -1;//判负环 } } } } return dis[ed]; } int main() { // freopen("note.in","r",stdin); // freopen("note.out","w",stdout); scanf("%d",&T); while(T--) { scanf("%d%d",&n,&d); for(int i=1;i<=n;++i) { scanf("%d",&a[i].h); a[i].pos=i; } tot=0,flag=1; memset(head,0,sizeof(head)); sort(a+1,a+n+1,cmp); //找到起点和终点 st=min(a[1].pos,a[n].pos); ed=max(a[1].pos,a[n].pos); for(int i=1;i<=n-1;++i) { add(i+1,i,-1); //从标号小的边向大的边连 int u=min(a[i].pos,a[i+1].pos); int v=max(a[i].pos,a[i+1].pos); if(d<v-u+a[i+1].h-a[i].h) { flag=0; break; } add(u,v,d-a[i+1].h+a[i].h); } if(flag) printf("%d ",spfa(st,ed)); else printf("-1 "); } } /* 2 3 4 3 2 4 3 4 3 2 6 */
完结撒花!