差分约束系统
例如，
5 6
20 34 54 10 15
这一组测试数据
先编号，分别为1 2 3 4 5 ，然后可以写出一组表达式，两个编号之间的距离必定大于等于1的，所以i+1到i建立有向边，权值为-1，然后进行结构体排序，根据高度来排序。然后相邻两个节点再写表达式，标号小的到标号大的之间建立有向边，权值为D，最后把高度最小的编号和高度最大的编号找出来，因为要求的是最大值，所以采用最短路来解决。把高度最小的编号设置为起点，求出到高度最大的编号的最短路，就是答案。如果存在环，就输出-1。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; const int maxn=;
const int INF=0x7FFFFFFF;
struct HH {int id,heights;}node[maxn];
struct abc {int startt,endd,costt;}dd[*maxn];
bool cmp(const HH&a,const HH&b){return a.heights<b.heights;}
vector<abc>ljb[maxn];
int ff[maxn],summ[maxn],dist[maxn];
int n,h,D,ss,ee,qd,zd;
int tyu; void spfa()
{
queue<int>Q;
while(!Q.empty()) Q.pop();
int i;
for(i=; i<=n; i++) dist[i]=INF;
memset(ff,,sizeof(ff));
memset(summ,,sizeof(summ));
dist[qd]=;
ff[qd]=;
Q.push(qd);
while(!Q.empty())
{
int hh=Q.front();
Q.pop();
summ[hh]++;
if(summ[hh]>n){tyu=;break;}
ff[hh]=;
for(i=; i<ljb[hh].size(); i++)
{
abc noww;
noww=ljb[hh][i];
if(dist[hh]+noww.costt<dist[noww.endd])
{
dist[noww.endd]=dist[hh]+noww.costt;
if(ff[noww.endd]==)
{
ff[noww.endd]=;
Q.push(noww.endd);
}
}
}
}
} int main()
{
int T,t;
scanf("%d",&T);
for(t=;t<=T;t++)
{
int i;
scanf("%d%d",&n,&D);
for(i=;i<=n;i++) ljb[i].clear();
for(i=;i<n;i++)
{
scanf("%d",&h);
node[i].id=i+;
node[i].heights=h;
}
int tott=;
for(i=;i<n-;i++)
{
dd[tott].startt=node[i+].id;
dd[tott].endd=node[i].id;
dd[tott].costt=-;
ljb[node[i+].id].push_back(dd[tott]);
tott++;
}
sort(node,node+n,cmp);
ss=node[].id;
ee=node[n-].id;
if(ss>ee) qd=ee,zd=ss;
else qd=ss,zd=ee;
for(i=;i<n-;i++)
{
if(node[i].id>node[i+].id)
{
dd[tott].startt=node[i+].id;
dd[tott].endd=node[i].id;
dd[tott].costt=D;
ljb[node[i+].id].push_back(dd[tott]);
tott++;
} else if(node[i].id<node[i+].id)
{
dd[tott].startt=node[i].id;
dd[tott].endd=node[i+].id;
dd[tott].costt=D;
ljb[node[i].id].push_back(dd[tott]);
tott++;
}
}
tyu=; spfa();
printf("Case %d: ",t);
if(tyu==)printf("%d\n",dist[zd]-dist[qd]);
else printf("-1\n");
}
return ;
}