您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

差分约束系统

就是不等式+spfa求最短路

为什么用spfa,因为这属于边问题;

这里讲一下建边;

1.x1-x2<3 得 x1<3+x2

2.x2-x3<-2 得x2<-2+x3

3.x1-x3<1 得 x1<x3+1

 第二种用Floyd但不建议速度慢超时

建边要建立反向边

  1. 除源点外的所有顶点最短距离初始化为 ∞∞,源点 d_1d1​ 最短距离为 00。
  2. 对边集 EE 进行 n-1n−1 次松弛操作。
  3. 检查是否存在负权边,即是否存在未收敛的点。若存在,说明图存在负环,原不等式组无解;否则 d_idi​ 即为 x_ixi​ 的一个解。
#include <bits/stdc++.h>
using namespace std;
struct edge { 
    int u, v, w; 
} e[5050];
int d[5050], n, m, c, c1, y;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &c, &c1, &y);
        e[i].u = c1, e[i].v = c, e[i].w = y;
    } for (int i = 1; i <= n; ++i) d[i] = (i == 1 ? 0 : 0x3f3f3f3f);
	for (int i = 1; i < n; ++i) 
	    for (int j = 1; j <= m; ++j)
	        d[e[j].v] = min(d[e[j].u] + e[j].w, d[e[j].v]);
    for (int i = 1; i <= m; ++i) 
	    if (d[e[i].v] > d[e[i].u] + e[i].w) 
	        return !printf("NO");
    for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进