没有概念，233，直接进入主题：
一般引入源点 s s s，令 x s = 0 x_s=0 xs=0，即 d i s [ s ] = 0 dis[s] = 0 dis[s]=0。
不等式转化建图 x u + w ≥ x v x_u + w \geq x_v xu+w≥xv a d d ( u , v , w ) add(u, v, w) add(u,v,w) x u + w > x v x_u + w > x_v xu+w>xv x u + ( w − 1 ) ≥ x v x_u + (w - 1) \geq x_v xu+(w−1)≥xv a d d ( u , v , w − 1 ) add(u, v, w - 1) add(u,v,w−1) x u = x v x_u = x_v xu=xv x u + 0 ≥ x v , x v + 0 ≥ x u x_u + 0 \geq x_v, x_v + 0 \geq x_u xu+0≥xv,xv+0≥xu a d d ( u , v , 0 ) , a d d ( v , u , 0 ) add(u, v, 0), add(v, u, 0) add(u,v,0),add(v,u,0) x u ≥ c x_u \geq c xu≥c x u − c ≥ x s x_u - c \geq x_s xu−c≥xs a d d ( u , s , − c ) add(u, s, -c) add(u,s,−c) x u ≤ c x_u \leq c xu≤c x s + c ≥ x u x_s + c \geq x_u xs+c≥xu a d d ( s , u , c ) add(s, u, c) add(s,u,c) x u x v ≥ w \cfrac{x_u}{x_v} \geq w xvxu≥w l o g x u − l o g x v ≥ l o g w logx_u - logx_v \geq logw logxu−logxv≥logw a d d ( u , v , − l o g w ) add(u, v, -logw) add(u,v,−logw)① 无解：存在负环 x v 1 , x v 2 , ⋯ , x v k x_{v1}, x_{v2}, \cdots, x_{vk} xv1,xv2,⋯,xvk，将负环上的边所代表的不等式组取出，即 { x v 1 + w 1 ≥ x v 2 x v 2 + w 2 ≥ x v 3 ⋯ x v k + w k ≥ x v 1 \begin{cases} x_{v1} + w_1 \geq x_{v2} \\ x_{v2} + w_2 \geq x_{v3} \\ \quad \quad\cdots\\ x_{vk} + w_k \geq x_{v1} \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧xv1+w1≥xv2xv2+w2≥xv3⋯xvk+wk≥xv1 不等式相加，得 ∑ i = 1 k w i ≥ 0 \sum\limits_{i=1}^{k} w_i \geq 0 i=1∑kwi≥0，而负环代表 ∑ i = 1 k < 0 \sum\limits_{i=1}^{k} \lt 0 i=1∑k<0。
附一个 b f s bfs bfs 版的 S P F A SPFA SPFA 判负环：
int spfa(){ queue<int> q; for(int i = 0; i <= n; ++i){ dis[i] = oo; num[i] = vis[i] = 0; } dis[0] = 0, q.push(0), vis[0] = num[0] = 1; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 0; for(auto &e : G[u]){ int v = e.second, w = e.first; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w, num[v] = num[u] + 1; if(num[v] > n + 1) return 1; // 结点编号 0 ~ n，共 n + 1 个 if(!vis[v]) q.push(v), vis[v] = 1; } } } return 0; }② 有解情况，跑最短路后， x i = d i s [ i ] x_i = dis[i] xi=dis[i] 即为一组可行解，且为最大值解。（如 x s + c ≥ x u x_s + c \geq x_u xs+c≥xu， s → u s \rightarrow u s→u 连权值 c c c 的边，松弛后 x u = c x_u = c xu=c）
附一道题：https://codeforces.com/gym/102394/problem/A
