POJ 3169 布局：差分约束 + Bellman-Ford 求最长路

题目大意

N 头牛（N ≤ 1000）按编号排成一排，位置可重合。ML 对好牛：距离 ≤ D；MD 对坏牛：距离 ≥ D。求牛 1 到牛 N 的最大可能距离。无解输出 -1，无上界输出 -2。

差分约束建模

设 d[i] 为第 i 头牛位置。约束转化为不等式组：

1. 顺序性：d[i] ≤ d[i+1] → d[i+1] - d[i] ≥ 0 → 边 i+1 → i 权 0
2. 好牛 (A,B,D)：d[B] - d[A] ≤ D → d[A] - d[B] ≥ -D → 边 B → A 权 -D
3. 坏牛 (A,B,D)：d[B] - d[A] ≥ D → d[B] - d[A] ≥ D → 边 A → B 权 D

目标：最大化 d[N] - d[1]，即求 1 到 N 的最长路。因有负权边，用 Bellman-Ford（或 SPFA）求最短路，取反即最长路。

算法流程

1. 建图：节点 0~N-1 对应牛 1~N
2. 初始化 d[0]=0，其余 INF
3. 松弛 N 轮：顺序边、好牛边、坏牛边
4. 判断结果：
   • d[0] < 0 → 负环 → 无解 (-1)
   • d[N-1] == INF → 无上界 (-2)
   • 否则输出 d[N-1]

C++ 实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;

#define INF 123456789
#define LL long long
const int MAXN = 1000 + 10;
const int MAXM = 10000 + 10;

int al[MAXM], bl[MAXM], dl[MAXM];
int ad[MAXM], bd[MAXM], dd[MAXM];
int d[MAXN];
int N, ML, MD;

void solve() {
    fill(d, d + N, INF);
    d[0] = 0;
    for (int iter = 0; iter < N; ++iter) {
        // 顺序约束：d[i+1] -> d[i] 权 0
        for (int j = 0; j + 1 < N; ++j)
            if (d[j+1] < INF) d[j] = min(d[j], d[j+1] + 0);
        // 好牛：al -> bl 权 dl
        for (int j = 0; j < ML; ++j)
            if (d[al[j]-1] < INF) d[bl[j]-1] = min(d[bl[j]-1], d[al[j]-1] + dl[j]);
        // 坏牛：bd -> ad 权 -dd
        for (int j = 0; j < MD; ++j)
            if (d[bd[j]-1] < INF) d[ad[j]-1] = min(d[ad[j]-1], d[bd[j]-1] - dd[j]);
    }
    int ans = d[N-1];
    if (d[0] < 0) ans = -1;          // 负环
    else if (ans == INF) ans = -2;   // 无上界
    printf("%d\n", ans);
}

int main() {
    while (scanf("%d%d%d", &N, &ML, &MD) != EOF) {
        for (int i = 0; i < ML; ++i) scanf("%d%d%d", &al[i], &bl[i], &dl[i]);
        for (int i = 0; i < MD; ++i) scanf("%d%d%d", &ad[i], &bd[i], &dd[i]);
        solve();
    }
    return 0;
}

关键点总结

• 差分约束系统：x_j - x_i ≤ c → 边 i → j 权 c，求最短路
• 最长路转最短路：目标最大化 d[N]-d[1]，建反向边求最短路
• 负环判定：第 N 次松弛仍能更新 → 负环 → 约束冲突
• 无上界判定：目标节点距离仍为 INF → 无路径约束 → 可无限远

复杂度

• 时间：O(N × (ML+MD+N)) ≤ 1000 × 21000 ≈ 2e7，1s 内通过
• 空间：O(N + ML + MD)