传送门 题意：在一条直线上有N个房子，每个房子的高度不一样，一个超人可以将这N个房子左右移动，但是不能改变房子的相对位置。位置都为整数点。同一位置不能有两个以上的房子两个超人从最矮的房子开始，跳到刚好比他所在房子高的房子上去，一直这样跳，每次跳到的房子都比现在所在的房子高，而且每次跳的水平距离不能超过D米。问：如何将这些房子进行合理的摆放(不改变相对位置的前提下)，使得超人能够经过所有的房子跳到最高的房子，又要使最矮的房子和最高的房子之间的距离最远? 题解：第一次写差分约束（居然是1A<(￣︶￣)>），先总结一句话：最短路达到可能的最大，最长路达到可能的最小。 对于这道题，对于每个i连一条(i+1，i，-1)的边，因为pos(i+1)-pos(i)≥1，然后对于按高度从小到大排序后的每个i，连一条(a[i].id，a[i+1].id，D)的边（保证其中a[i].id < a[i+1].id，给图定向？）。然后跑最短路即可。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int MAXN=1002,INF=0x3f3f3f3f; int n; int head[MAXN],edge=0; struct EDGE { int v,nxt,w; }e[MAXN<<1]; int dis[MAXN],in[MAXN],source,sink,len; bool vis[MAXN]; struct Data { int h,id; friend bool operator <(const Data &a,const Data &b) { return a.h<b.h; } }a[MAXN]; inline void adde(int u,int v,int w) { e[++edge].nxt=head[u],e[edge].v=v,e[edge].w=w,head[u]=edge; } inline int spfa(int source,int sink) { memset(vis,false,sizeof(vis)); memset(dis,INF,sizeof(dis)); memset(in,0,sizeof(in)); queue<int> q; q.push(source),dis[source]=0,vis[source]=true,++in[source]; while (!q.empty()) { int p=q.front(); q.pop(); vis[p]=false; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (dis[v]>dis[p]+e[i].w) { dis[v]=dis[p]+e[i].w; if (!vis[v]) { vis[v]=true; q.push(v); if (++in[v]>n) return -1; } } } } return dis[sink]; } int main() { // freopen("hdu 3440.in","r",stdin); int kase,tt=0; scanf("%d",&kase); while (kase--) { edge=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&len); for (int i=1;i<=n;++i) { scanf("%d",&a[i].h); a[i].id=i; if (i^n) adde(i+1,i,-1); } sort(a+1,a+n+1); for (int i=1;i<n;++i) { int u=a[i].id,v=a[i+1].id; if (u>v) u^=v^=u^=v; adde(u,v,len); } source=a[1].id,sink=a[n].id; if (source>sink) source^=sink^=source^=sink; printf("Case %d: %d\n",++tt,spfa(source,sink)); } return 0; }