poj3169-所谓的差分约束，但是感觉题目各种问题
题目很好理解，转换为差分约束也好理解。关键是差分约束是要n+1个点，多一个v0，但是如果按照差分去做，肯定会wa，因为这样做以后，样例肯定都过不了，想想看，v0到其他点距离为0，所以到v1最短为0，v4最短为0，怎么求都得不到最后的27啊？？？？？
还有像vj>=vi(j >= i)这些约束不用加，这个好理解，证明题目中没给这一块的测试用例，数据弱没关系，但是如果你加上了，可能会报错。
discuss好多疑问，，但是无人解决，只能说这题目还是有争议的。
一个解释：
差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。也就是开始各点不符合条件，后来通过减小变得符合了，所以一定是符合条件的最大值。既然是求最大值，并且是减小各点距离，也就是把各点由数轴的右侧向左侧拉，所以我们一定要选择一个最终在数轴最左侧的点，并初始化为0，把所有正无穷的点拉近到符合不等式。最长路同理。
一肚子疑问，虽然如此，但是还是对差分约束有了了解，就是给出一些不等式类似xj-xi<=wb 这样的，能够通过求最短路获得其中的一组解，这也是数学计算机化的一种表现吧。
无语。。。。。忘牛人指示，下面是没有按照差分约束概念做的，a了，但是感觉好不爽，疑问很多。。。
[cpp]
#include <stdio.h>
#define maxN 1100
#define inf 1000000000
struct EDGE
{
int v, w, next;
}edge[20 * maxN];
int preEdge[maxN];
int dis[maxN];
int edgeNum;
bool vis[maxN];
int queue[20 * maxN];
int cnt[maxN];
int N;
void Init()
{
for (int i = 1; i <= N; ++ i)
{
dis[i] = inf;
vis[i] = false;
preEdge[i] = 0;
cnt[i] = 0;
}
}
bool spfa()
{
int head = 0, tail = 1;
queue[0] = 1;
dis[1] = 0;
while (head < tail)
{
int u = queue[head];
vis[u] = true;
int p = preEdge[u];
while (p != 0)
{
int v = edge[p].v;
int w = edge[p].w;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
if (!vis[v])
{
vis[v] = true;
queue[tail] = v;
tail ++;
}
if (++ cnt[v] > N)
{
return false;
}
}
p = edge[p].next;
}
vis[u] = false;
head ++;
}
return true;
}
void addEdge(int u, int v, int w)
{
edge[edgeNum].v = v;
edge[edgeNum].w = w;
edge[edgeNum].next = preEdge[u];
preEdge[u] = edgeNum ++;
//edgeNum ++;
}
int main()
{
int ML, MD;
while (scanf("%d%d%d", &N, &ML, &MD) != EOF)
{
edgeNum = 1;
int u, v, w;
Init();
for (int i = 0; i < ML; ++ i)
{
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
}
for (int i = 0; i < MD; ++ i)
{
scanf("%d%d%d", &u, &v, &w);
addEdge(v, u, -w);
}
//for (int i = 2; i <= N; ++ i)
//{
// addEdge(i, 1, 0);
// addEdge(i,i - 1, 0);
//}
if(!spfa())
printf("-1\n");
else if (dis[N] == inf)
{
printf("-2\n");
}
else
printf("%d\n", dis[N]);
}
return 0;
}
作者：zhang20072844
补充：软件开发 , C++ ,
