P5960 【模板】差分约束

题目描述

给出一组包含 m 个不等式，有 n 个未知数的形如：

的不等式组，求任意一组满足这个不等式组的解。

Read more: P5960 【模板】差分约束

解答

差分约束问题的核心是将不等式转化为图论中的边，然后通过求单源最短路来求解：

1. 不等式转化：把$x_c​−x_{c′}​≤y$变形为$x_c​≤x_{c′}​+y$，这对应图中从节点c′到c的一条有向边，边权为y。
2. 虚拟源点：为了保证图的连通性（所有节点都能被遍历到），新增一个虚拟源点0，向所有节点1∼n连一条边权为0的边（即xi​≤x0​+0，等价于xi​≤0，不影响原不等式组的解）。
3. 判环与求解：从虚拟源点0出发求单源最短路：
   • 若图中存在负权回路，说明不等式组无解；
   • 若无负权回路，则每个节点的最短路值就是一组可行解。

求解最短路时，要求能够判断负环，使用 Bellman-Ford 或 SPFA 算法。

Bellman-Ford

初始化：先给所有节点的 “当前最短路径”（dist[i]） 赋值为 “无穷大”，只有源点的最短路径设为 0（自己到自己距离为 0）。

多轮松弛更新：

• 进行 n-1 轮更新（称为 “松弛”，n为节点总数）；
• 每一轮都遍历图中所有的边：对每条边（设从节点 A 到 B，边权为 W），检查 “从源点到 A 的最短路径 + W” 是否比 “当前记录的源点到 B 的最短路径” 更短；如果是，就更新 B 的最短路径。
• 优化点：如果某一轮遍历完所有边后，没有任何节点的最短路径被更新，说明所有最短路已经找到，可以提前结束，不用走完 n-1 轮。

检测负权回路：

• 完成 节点总数-1 轮更新后，再额外遍历一次所有边；
• 如果这一轮还能更新某个节点的最短路径，说明存在负权回路（因为正常情况下，n-1 轮已经能找到所有最短路，还能更新就意味着存在负环）。

SPFA

Bellman-Ford算法的优化。

Bellman-Ford 效率低的关键是 “每轮遍历所有边”，但实际上：只有某个节点的最短路径被更新后，以这个节点为起点的边，才有可能更新它的邻接节点的最短路径。

SPFA 就是抓住这个特点，用 “队列” 记录 “刚刚被更新过最短路径的节点”，只处理这些节点的出边，避免遍历无用的边。

AC代码

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

const int mm=5050;
int n,m;
vector<pair<int,int>> e[mm];
int dist[mm];

bool SPFA(){
    for (int i=1; i<=n; i++) {
        dist[i]=1e8;
    }
    
    unordered_set<int> q;

    q.insert(0);
    for (int i=0; i<n+1; i++) {
        if (q.empty()) break;
        unordered_set<int> newq;
        for (int j : q) {
            for (auto k : e[j]) {
                int newdist=dist[j]+k.second;
                if(dist[k.first]>newdist){
                    dist[k.first]=newdist;
                    newq.insert(k.first);
                }
            }
        }
        q=std::move(newq);
    }

    if (!q.empty()){
        return false;
    }
    return true;
}

int main(){
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        int c, c1, y;
        cin>>c>>c1>>y;
        e[c1].push_back(make_pair(c, y));
    }

    for (int i=1; i<=n; i++) {
        e[0].push_back(make_pair(i, 0));
    }

    if (SPFA()){
        for (int i=1; i<=n; i++) {
        cout<<dist[i]<<' ';
        }
    } else {
        cout<<"NO";
    }

    return 0;
}