洛谷 P5960 [模板] 差分约束 题解 SPFA

【模板】差分约束

题目描述

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

$$\{\begin{array}{l}{x}_{c_1}-x_{c_1^{\prime }}\le y_1\\ x_{c_2}-x_{c_2^{\prime }}\le y_2\\ \cdots \\ x_{c_m}-x_{c_m^{\prime }}\le y_m\end{array}$$

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

输入格式

第一行为两个正整数 $n,m$，代表未知数的数量和不等式的数量。

接下来 $m$ 行，每行包含三个整数 $c,c^{\prime },y$，代表一个不等式 $x_c-x_{c^{\prime }}\le y$。

输出格式

一行，$n$ 个数，表示 $x_1,x_2\cdots x_n$ 的一组可行解，如果有多组解，请输出任意一组，无解请输出 NO。

样例 #1

样例输入 #1

3 3
1 2 3
2 3 -2
1 3 1

样例输出 #1

5 3 5

提示

样例解释

$\{\begin{array}{l}{x}_1-x_2\le 3\\ x_2-x_3\le -2\\ x_1-x_3\le 1\end{array}$

一种可行的方法是 $x_1=5,x_2=3,x_3=5$。

$\{\begin{array}{l}5-3=2\le 3\\ 3-5=-2\le -2\\ 5-5=0\le 1\end{array}$

数据范围

对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^3$，$-10^4\le y\le 10^4$，$1\le c,c^{\prime }\le n$，$c\ne c^{\prime }$。

原题

洛谷P5960——传送门

思路

例如，将$x_1-x_2\le 3$看作是x2到x1的有向边，并且边权为3，这样就可以保证通过最短路SPFA求解时x2到x1的最短路长度一定小于等于3，也就是满足了该不等式条件。而求解整个不等式组便可以转化为求解到 x_i 的最短路径。其中无解的情况就是存在负环，否则有解。

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);

const int maxn = 5e3 + 6;
const int maxm = 5e3 + 6;

int n, m; // 点的个数，有向边的个数

struct edge
{
    int to, len; // to为边的指向，len为边的长度即边权
};

vector<edge> e[maxn]; // 存储以点i为起点的边

ll minDis[maxn]; // 从起点到第i个点的最短路长度
bool vis[maxn];  // 第i个点是否在队列中
int cnt[maxn];   // 记录某个点的入队次数，若次数大于等于n，存在负环

bool spfa()
{
    memset(minDis, 0x3f, sizeof(minDis));
    minDis[0] = 0; // 以超级源点为起点
    queue<int> q;
    q.push(0);
    vis[0] = 1;
    cnt[0]++;
    while (!q.empty())
    {
        int st = q.front();
        q.pop();
        vis[st] = 0;          // 已出队，vis赋值0
        for (edge eg : e[st]) // 遍历以st为起点的所有有向边
        {
            int ed = eg.to;
            int weight = eg.len;
            if (minDis[st] + weight < minDis[ed]) // 判断是否可以更新最短路长度
            {
                minDis[ed] = minDis[st] + weight;
                if (!vis[ed]) // 如果已经在队列中，则不需要再加入队列
                {
                    q.push(ed);
                    vis[ed] = 1;      // 记录在队列中
                    cnt[ed]++;        // 加入队列的次数++
                    if (cnt[ed] >= n) // 入队次数>=n，存在负环，返回0
                    {
                        return 0;
                    }
                }
            }
        }
    }

    return 1; // 不存在负环，返回1
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    int u, v, w; // 从u到v的权值为w的有向边
    while (m--)
    {
        cin >> v >> u >> w;
        e[u].push_back({v, w});
    }
    // 以0为超级源点，该点到其他所有点的距离设置为0
    for (int i = 1; i <= n; i++)
    {
        e[0].push_back({i, 0});
    }

    if (spfa()) // 最短路的答案即为方程的一组解
    {
        for (int i = 1; i <= n; i++)
        {
            if (i != n)
                cout << minDis[i] << ' ';
            else
                cout << minDis[i] << '\n';
        }
    }
    else // 有负环，则无解
        cout << "NO" << '\n';

    return 0;
}