tk's blog
  • tk's blog Read Me
  • 算法相关
    • 数据结构
      • 【集训整理】 旋转treap模板
      • 二叉树及相关数据结构的java语言实现
      • 快乐树0x01:AVL树的java实现
      • 快乐树0x02 线段树实现(c++)
      • 链表的Java语言实现
    • 算法
      • DP的背包问题小结-java语言描述
      • 【集训整理】2-SAT问题 模板题
      • 【集训整理】Tarjan算法 模板题
      • 【集训整理】差分约束 模板题
      • 【集训整理】最近公共祖先LCA 模板题
      • 二分查找与二分答案-java实现
      • 动态规划-java语言练习一:暴力DP
      • 快速幂
      • 状态压缩DP-java描述
      • 差分
      • 乘法逆元
    • 题解
      • CFRound-GoodBye2022题解
  • java相关
    • Java与算法竞赛——注意事项摘录
    • java面向对象简要总结 一
    • java面向对象简要总结 三
    • java面向对象简要总结 二
  • 后端相关
    • Linux-Crontab命令
    • Spring Data JPA 使用方法
    • Spring集成Artemis实现JSM的异步消息传递
    • Spring使用自定义配置项
    • MIT6.824分布式系统Lab1.MapReduce笔记
    • MIT6.824分布式系统Lab2-Raft-A笔记
    • MIT6.824分布式系统Lab2-Raft-B笔记
  • 杂谈
    • 杂谈-关于2021
  • 杂项
    • c语言 scanf的返回值
    • 系统设计
  • 计科基础
    • 编译原理
      • 编译原理:词法分析笔记
    • CSAPP 第二章笔记
    • 计算机组成原理笔记
    • CSAPP Lab1. Datalab
    • CSAPP Lab2 Bomblab
  • C++每日一题
    • C++每日一题 Day 1 肥宅水
    • C++每日一题 Day 2 数字反转
    • C++每日一题 Day 3 理五的凡尔赛风气
    • C++每日一题 Day 4 我喜欢这个数
    • C++每日一题 Day 5 数字楼梯
    • C++每日一题 Day 6 插火把
    • C++每日一题 Day 7 贪吃蛇
    • C++每日一题 Day 8 蒙德最强战力
    • C++每日一题 Day 9 璃月七星选举
    • C每日一题 Day 2 肥宅水
    • C每日一题 Day 3 理五的凡尔赛风气
    • C语言每日一题 Day 1 荧妹好感队
由 GitBook 提供支持
在本页
  1. 算法相关
  2. 算法

【集训整理】差分约束 模板题

上一页【集训整理】Tarjan算法 模板题下一页【集训整理】最近公共祖先LCA 模板题

最后更新于2年前


题面:

m 个约束条件,第 j 个约束条件有三个整数_u_,v,w,表示a_u−a_v≤w a\_u-a\_v\le wa_u−a_v≤w

请判断是否至少存在一组 _a_的值满足上述条件。

差分约束系统是一种特殊的n元一次不等式组,包含n个变量及m个约束条件。其中约束条件是由其中两个变量作差构成 ,如x_i−x_j<=c_kx\_i-x\_j<=c\_kx_i−x_j<=c_k

这个x_i−x_j<=c_kx\_i-x\_j<=c\_kx_i−x_j<=c_k 和最短路的三角不等式dist\[y]<=dist\[x]+z 相似,所以可以把每个变量都看作一个点,每个约束条件相当于从节点iii向节点i连一条长度为c_kc\_kc_k的有向边。判断无解只需要判断图中是否存在负环就可以了。

为了避免不联通的情况,设一个新点n+1,然后让他向每个点都连一条边权为0的边。

所以就把一个不等式组的问题变成了图的问题。对n+1号点跑一遍单源最短路,使用SPFA,判断是否存在负环即可。

SPFA的原版方法:

将起点入队,每次从队列里取一个点,尝试更新(松弛)与这个点连接的所有点的最短路径长度。如果松弛成功,那么将这个点入队(当然,如果队列里已经有了,那就没必要再入队了。用一个数组记录这个数是否已经在队列里了)。

用SPFA求负环的方法:

对于负环,SPFA会对他反复松弛,使最短路变小。所以我们只要记录一下每个节点松弛的次数,如果某个点的松弛次数>n了,那肯定是有负环了。

#include<iostream>
#include<queue>
#include<cstring>
#define N 51000
using namespace std;

int v[N], w[N], nex[N];
int d[N], cnt[N], first[N];
bool vis[N]; int t;
int n,m;

void add(int x, int y, int z){
    t++;
    nex[t] = first[x];
    first[x] = t;
    v[t] = y;
    w[t] = z;
}

bool SPFA(int s){
    int x, y, i, j;
    queue<int>q;
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    while (!q.empty())  q.pop();
    d[s] = 0;
    cnt[s] = 1;
    q.push(s);
    vis[s] = true;
    while (!q.empty()){
        x = q.front();
        q.pop();
        vis[x] = false;
        for (i = first[x]; i; i = nex[i]){
            y = v[i];
            if (d[y] > d[x] + w[i]){
                d[y] = d[x] + w[i];
                cnt[y] = cnt[x] + 1;
                if (cnt[y] > n)
                    return false;
                if (!vis[y]){
                    q.push(y);
                    vis[y] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> b >> a >> c;
        add(a, b, c);
    }
    d[n + 1] = 0;
    for (int i = 1; i <= n; i++) add(n + 1, i,0);
    if (SPFA(n+1))
        cout << "YES";
    else
        cout << "NO";
}