当前位置: 首页 > news >正文

差分约束模板

洛谷模板测试七倍经验
https://www.luogu.com.cn/record/238785118
https://www.luogu.com.cn/record/238783283
https://www.luogu.com.cn/record/238788990
https://www.luogu.com.cn/record/238791631
https://www.luogu.com.cn/record/238792334
https://www.luogu.com.cn/record/238792639
https://www.luogu.com.cn/record/238794596

struct DiffConstraints {int n;std::vector<std::vector<std::array<int, 2>>> adj;std::vector<int> cnt, in, d;DiffConstraints() : n(0) {}DiffConstraints(int n_) {init(n_);}void init(int n_) {n = n_;adj.resize(n);cnt.assign(n, 0);in.assign(n, 0);d.assign(n, 0);}void add(int a, int b, int c) {adj[a].push_back({b, c});}// 添加约束 x_a - x_b <= cvoid addConstraint(int a, int b, int c) {add(b, a, c);}bool spfa(int u, int k) {std::queue<int> q;cnt.assign(n, 0);in.assign(n, 0);q.push(u);in[u] = 1;while (!q.empty()) {int u = q.front();q.pop();in[u] = 0;for (const auto& [v, w] : adj[u]) {if (d[v] < d[u] + w * k) {d[v] = d[u] + w * k;if (!in[v]) {if (++cnt[v] > n) return false;in[v] = 1;q.push(v);}}}}return true;}//求解最小值(最长路)(即spfa边权转化为负的跑最短路)bool solveMin(int u = 0) {d.assign(n, -0x3f3f3f3f);d[u] = 0;return spfa(u, -1);}//求解最大值(最短路)bool solveMax(int u = 0) {d.assign(n, 0x3f3f3f3f);d[u] = 0;return spfa(u, 1);}int dis(int x) {return d[x];}
};
http://www.hskmm.com/?act=detail&tid=25009

相关文章:

  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025
  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程