题目来源：HDU 3592 World Exhibition
题意：若干限制条件 求1到n的最大距离
思路：直接差分约束
这里收集了某大牛的总结
/* 题意：求符合题意的最小集合的元素个数 题目要求的是求的最短路， 则对于 不等式 f(b)-f(a)>=c,建立 一条 b 到 a 的边 权值为 c,则求的最长路 即为 最小值(集合) 并且有隐含条件：0<=f(a)-f(a-1)<=1 则有边权关系(a,a-1,0)以及(a-1,a,-1); 将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大 差分约束 在实际的应用中，一般使用SPFA(Shortest Path Fast Algorithm)算法来实现。 差分约束系统中源点到每个点的距离确定 关于Dist[]的初始化化 1.如果将源点到各点的距离初始化为0，最终求出的最短路满足 它们之间相互最接近了 2.如果将源点到各点的距离初始化为INF(无穷大)，其中之1为0，最终求出的最短路满足 它们与该点之间相互差值最大。 3.差分约束系统的确立要根据自己确定的约束条件，从约束点走向被约束点 连边一般有两种方法，第一种是连边后求最长路的方法，第二种是连边后求最短路的方法。 例：d[x]-d[y]>=Z 如果想连边后求最长路 那么将不等式变形为这种形式 d[x]>=d[y]+z y---x连一条权值为z的边 求最短路则变形成d[y]<=d[x]-z x---y连一条权值为-z的边。 如果是别的不等式，也可以根据情况变形。但是要保证的是 两个变量（x,y)的系数一定要是正的。而常量则不一定。 第一： 感觉难点在于建图 第二： ①：对于差分不等式，a - b <= c ，建一条 b 到 a 的权值为 c 的边，求的是最短路，得到的是最大值 ②：对于不等式 a - b >= c ，建一条 b 到 a 的权值为 c 的边，求的是最长路，得到的是最小值 ③：存在负环的话是无解 ④：求不出最短路（dist[ ]没有得到更新）的话是任意解 第三： 一种建图方法： 设x[i]是第i位置（或时刻）的值（跟所求值的属性一样），那么把x[i]看成数列，前n项和为s[n]，则x[i] = s[i] - s[i-1]； 那么这样就可以最起码建立起类似这样的一个关系：0 <= s[i] - s[i-1] <= 1; 其他关系就要去题目探索了 */
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1010;
const int INF = 999999999;
struct edge
{
int v, w;
};
vector <edge> G[maxn];
bool inq[maxn];
int d[maxn];
int cnt[maxn];
int n, s, e;
bool SPFA()
{
memset(inq, false, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i <= n; i++)
d[i] = INF;
d[1] = 0;
queue <int> Q;
Q.push(1);
inq[1] = true;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i].v;
int w = G[u][i].w;
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
if(!inq[v])
{
inq[v] = true;
Q.push(v);
if(++cnt[v] > n)
return false;
}
}
}
}
return true;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int x, y;
scanf("%d %d %d", &n, &x, &y);
for(int i = 0; i <= n; i++)
G[i].clear();
for(int i = 0; i < x; i++) // d[v] - d[u] <= w
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
G[u].push_back((edge){v, w});
}
for(int i = 0; i < y; i++)//d[v] - d[u] >= w == d[u] - d[v] <= -w
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
G[v].push_back((edge){u, -w});
}
for(int i = 1; i < n; i++)//d[i] - d[i-1] >= 0 == d[i-1] - d[i] <= 0
G[i+1].push_back((edge){i, 0});
if(SPFA())
{
if(d[n] == INF)
puts("-2");
else
printf("%d\n", d[n]);
}
else
puts("-1");
}
return 0;
}
HDU 3592 World Exhibition 差分约束基础题,布布扣,bubuko.com
HDU 3592 World Exhibition 差分约束基础题
原文：http://blog.csdn.net/u011686226/article/details/24184117