SPFA

---

title: SPFA
categories:
- ICPC
tags:
- null
abbrlink: 33b8c865
date: 2024-09-04 00:00:00

SPFA

最短路:保证数据不存在负环的情况下，求1-n最短路

struct edge {
    int v, w;
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }
    vector<int> dis(n + 1, inf);
    auto spfa = [&]() {
        vector<bool> st(n + 1);
        queue<int> q;
        q.push(1);
        st[1] = true;
        dis[1] = 0;
        while (q.size()) {
            auto u = q.front();
            q.pop();
            st[u] = 0;
            for (auto [v, w] : e[u]) {
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    if (st[v] == 0) {
                        q.push(v);
                        st[v] = true;
                    }
                }
            }
        }
        if (dis[n] == inf)
            return false;
        return true;
    };
    for (int i = 1; i <= n; i++) deb(i, dis[i]);
    if (spfa())
        cout << dis[n] << endl;
    else
        cout << "impossible" << endl;
}

判断全局图中是不是存在负环

struct edge {
    int v, w;
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
    }
    vector<int> dis(n + 1, inf);
    vector<int> cnt(n + 1);
    auto judgefu = [&]() {
        vector<bool> st(n + 1, 1);
        queue<int> q;
        for (int i = 1; i <= n; i++) q.push(i);
        while (q.size()) {
            auto u = q.front();
            q.pop();
            st[u] = 0;
            for (auto [v, w] : e[u]) {
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n)
                        return true;
                    if (st[v] == 0) {
                        q.push(v);
                        st[v] = true;
                    }
                }
            }
        }
        return false;
    };
    if (judgefu())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

从顶点 1出发能到达的负环

struct edge {
    int v, w;
};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        if (w >= 0)
            e[v].push_back({u, w});
    }
    vector<int> dis(n + 1, inf);
    vector<int> cnt(n + 1);
    auto judgefu = [&]() {
        vector<bool> st(n + 1, 0);
        queue<int> q;
        q.push(1);
        st[1] = 1;
        dis[1] = 0;
        while (q.size()) {
            auto u = q.front();
            q.pop();
            st[u] = 0;
            for (auto [v, w] : e[u]) {
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n)
                        return true;
                    if (st[v] == 0) {
                        q.push(v);
                        st[v] = true;
                    }
                }
            }
        }
        return false;
    };
    if (judgefu())
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

• 差分约束

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

$$ \begin{cases} x_{c_1}-x_{c’1}\leq y_1 \x{c_2}-x_{c’2} \leq y_2 \ \cdots\ x{c_m} - x_{c’_m}\leq y_m\end{cases}$$

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

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

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

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

一、 求不等式组的可行解

！！！源点需要满足的条件：从源点出发，一定可以走到所有的边。！！！

步骤：
1. 先将每个不等式 $x_i \le x_j + c_k$，转化成一条从 $x_j$ 走到 $x_i$，长度为 $c_k$ 的边。
2. 找到一个超级源点，使得该源点一定可以遍历到所有边
3. 从源点求一遍单源最短路

结果1：如果存在负环，则原不等式组一定无解
结果2：如果没有负环，则 $dist[i]$ 就是原不等式组的一个可行解

---

二、 如何求最大值或者最小值，这里的最值指的是每个变量的最值(独立但可以同时取到)

结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。

问题：如何转化 $x_i \le c$，其中 $c$ 是一个常数，这类的不等式。

方法：建立一个超级源点0，然后建立 0 -> i 的边，长度是 $c$ 即可。

以求 $x_i$ 的最大值为例：

求所有从 $x_i$ 出发，构成的多个形如如下的不等式链

$$
x_i \le x_j +c_1 \le x_k + c_2 + c_1 \le ··· \le x_0 + c_1 + c_2 + ··· + c_m \qquad(x_0 = 0)
$$

所计算出的上界，最终 $x_i$ 的最大值等于所有上界的最小值。
这里所有上界的最小值可以理解这么一个例子：

把上述转换成图论的问题，就是求 $dist[i]$ 的最小值，即最短路求解

• 求 $x_i$ 的最小值 时则完全相反，求一个形如如下不等式链所计算出的下界，最终在所有下界里取最大值

$$
x_i \ge x_j +c_1 \ge x_k + c_2 + c_1 \ge ··· \ge x_0 + c_1 + c_2 + ··· + c_m \qquad(x_0 = 0)
$$

转换成图论的问题，就是求 $dist[i]$ 的最大值，即最长路求解

建边技巧：

• 如何转化 $x_i \le c$，其中 $c$ 是一个常数，这类的不等式。

  方法：建立一个超级源点0，然后建立 0 -> i 的边，长度是 $c$ 即可。

• $$ x_a-x_b \ge c \to x_b \le x_a-c \to addedge(a,b,-c)$$

• $$ x_a-x_b \le c \to addedge(b,a,c)$$

• $$x_a=x_b \to addedge(a,b,0) \and addedge(b,a,0) $$