POJ3169 Layout 差分约束

题意：有N头牛，这些牛都拥有一个属性x表示其在坐标轴上的坐标。现在给定ML组约束条件表示A、B两头牛坐标之差不能够超过C；MD组约束条件表示A、B两头牛坐标之差不能小于C，现在问1和N号牛之间最长的距离为多大，如果存在则输出最大长度，如果任意输出-2，如果已知条件存在矛盾输出-1。

解法：根据已知条件建立约束系统，问题在于形容两个点之间的距离看似是一种双向边的关系，但是如果一旦建立双向的负边那么就会发生错判了，这显然是错误的，因此我们只能够建立单向的边。为每一个点都选择一个参考点，我选择N号点作为参考点，那么每个点的相对距离就变成了与N号点的距离之差，所有边就都成为了从编号小的点指向编号大的点，这样便就是单向的了。加上隐含条件，两点之间的距离不能为负数，图就构好了。

代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int N, ML, MD;
int idx, head[10005];

struct Edge {
    int v, ct, next;
}e[2050005];

void insert(int a, int b, int ct) {
    e[idx].v = b, e[idx].ct = ct;
    e[idx].next = head[a];
    head[a] = idx++;
}

#include <queue>
int dis[10005], cnt[10005];
char vis[10005];

bool spfa() {
    memset(vis, 0, sizeof (vis));
    memset(cnt, 0, sizeof (cnt));
    memset(dis, 0x3f, sizeof (dis));
    queue<int>q;
    q.push(N);
    vis[N] = 1, dis[N] = 0, cnt[N] = 1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        if (cnt[v] > N) return false;
        vis[v] = 0;
        for (int i = head[v]; i != -1; i = e[i].next) {
            if (dis[e[i].v] > dis[v] + e[i].ct) {
                dis[e[i].v] = dis[v] + e[i].ct;
                if (!vis[e[i].v]) {
                    vis[e[i].v] = 1;
                                        ++cnt[e[i].v];
                    q.push(e[i].v);
                }
            }
        }
    }
    return true;
}

int main() {
    int a, b, c;
    while (scanf("%d %d %d", &N, &ML, &MD) != EOF) {
        idx = 0;
        memset(head, 0xff, sizeof (head));
        for (int i = 0; i < ML; ++i) {
            scanf("%d %d %d", &a, &b, &c);
            if (a > b) swap(a, b); // 选择N作为参考点，因此所有的双边距离约束均为从小到大
            insert(b, a, c);
            insert(a, b, 0);
        }
        for (int i = 0; i < MD; ++i) {
            scanf("%d %d %d", &a, &b, &c);
            if (a > b) swap(a, b);
            insert(a, b, -c);
        }
        if(!spfa()) {
            printf("-1\n");
        } else if(dis[1] == 0x3f3f3f3f) {
            printf("-2\n");
        }
        else {
            printf("%d\n", dis[1]);
        }
    }
    return 0;
}