差分约束
\(\text{luogu-5960}\)
给出一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：
的不等式组，求任意一组满足这个不等式组的解。
\(1 \le n,m \le 5 \times 10^3\)，\(-10^4 \le y \le 10^4\)，\(1 \le c,c' \le n\)，\(c \ne c'\)。
考虑将差分约束系统变形一下：
可以发现这个形式实际上跟最短路的不等式 \(dis_y \le dis_x + w\) 非常相似。
因此我们就将这个问题转化为一个求最短路的问题，我们连一条 \(j \to i\) 权值为 \(y_k\) 的边。
然后建一个虚点 \(0\)，连接所有点且边权为 \(0\)，从 \(0\) 开始跑 \(\text{spfa}\) 即可。
关于无解情况，若图存在负环，则查分约束系统无解，过程中用 \(\text{spfa}\) 判负环即可。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 5005
#define pii pair<long long, long long>
#define fi first
#define se secondlong long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}long long n, m, dis[MAXN], cnt[MAXN];
vector<pii > v[MAXN];
bool vis[MAXN];bool spfa(long long s) {memset(dis, 0x3f, sizeof dis);queue<long long> q; q.push(s);dis[s] = 0, vis[s] = true;while(!q.empty()) {long long x = q.front(); q.pop();vis[x] = false;for(auto it : v[x]) {long long y = it.fi, w = it.se;if(dis[y] > dis[x] + w) {dis[y] = dis[x] + w, cnt[y] = cnt[x] + 1;if(cnt[y] >= n + 1) return true;if(!vis[y]) q.push(y), vis[y] = true;}}}return false;
}int main() {n = read(), m = read();for(int i = 1; i <= n; i ++) v[0].push_back({i, 0});for(int i = 1; i <= m; i ++) {long long y = read(), x = read(), w = read();v[x].push_back({y, w});}if(spfa(0)) { cout << "NO\n"; return 0; }for(int i = 1; i <= n; i ++) cout << dis[i] << " ";cout << "\n";return 0;
}
\(\text{luogu-3275}\)
幼儿园里有 \(N\) 个小朋友，\(\text{lxhgww}\) 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，\(\text{lxhgww}\) 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，\(\text{lxhgww}\) 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入的第一行是两个整数 \(N,K\)。接下来 \(K\) 行，每行 \(3\) 个数字 \(X,A,B\)，表示小朋友们的要求。
- 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多；
- 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果；
- 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果；
- 如果 \(X=4\)， 表示第 \(A\) 个小朋友分到的糖果必须多于第 \(B\) 个小朋友分到的糖果；
- 如果 \(X=5\)， 表示第 \(A\) 个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果；
\(1\leq N,K\leq10^5, 1\leq X\leq5, 1\leq A, B\leq N\)。
首先它是个差分约束系统，要求变量总和最小就跑最长路。
但是它边权只有 \(0\) 或 \(1\)，考虑这个图有什么特殊性质。
先缩点，每个 SCC 内部如果出现了一条 \(u\) 到 \(v\) 的边权为 \(1\)，根据 SCC 的定义，一定还存在一条 \(v\) 到 \(u\) 的路径，由于边权 \(\geq 0\)，所以一定会出现一个正权环，则这个差分约束系统无解。
否则的话，发现 SCC 内部变量取值一定是相同的，那么问题变成了一个 DAG 上最长路，拓扑排序即可。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 100005
#define pii pair<long long, long long>
#define fi first
#define se secondlong long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}long long n, m, dfn[MAXN], low[MAXN], dn, s[MAXN], is[MAXN];
long long cnt, top, scc[MAXN], d[MAXN], sz[MAXN], dis[MAXN];
vector<pii > v[MAXN], g[MAXN];void tarjan(long long x) {dfn[x] = low[x] = ++ dn, s[++ top] = x, is[x] = 1;for(auto y : v[x]) if(!dfn[y.fi]) tarjan(y.fi), low[x] = min(low[x], low[y.fi]);else if(is[y.fi]) low[x] = min(low[x], dfn[y.fi]);if(dfn[x] == low[x]) {cnt ++;do {scc[s[top]] = cnt, sz[cnt] ++, is[s[top]] = 0;} while(s[top --] != x);}return;
}void topu() {queue<long long> q;for(int i = 1; i <= cnt; i ++) if(!d[i]) q.push(i);while(!q.empty()) {long long x = q.front(); q.pop();for(auto it : g[x]) {long long y = it.fi, w = it.se;d[y] --, dis[y] = max(dis[y], dis[x] + w);if(!d[y]) q.push(y);}}return;
}int main() {n = read(), m = read();for(int i = 1; i <= n; i ++) v[0].push_back({i, 1});for(int i = 1; i <= m; i ++) {long long x = read(), a = read(), b = read();if(x == 1) v[a].push_back({b, 0}), v[b].push_back({a, 0});else if(x == 2) v[a].push_back({b, 1});else if(x == 3) v[b].push_back({a, 0});else if(x == 4) v[b].push_back({a, 1});else v[a].push_back({b, 0});}tarjan(0);for(int x = 0; x <= n; x ++) for(auto it : v[x]) {long long y = it.fi, w = it.se;if(scc[x] == scc[y] && w) { cout << "-1\n"; return 0; }if(scc[x] != scc[y]) g[scc[x]].push_back({scc[y], w}), d[scc[y]] ++;}topu(); long long ans = 0;for(int i = 1; i <= cnt; i ++) ans += dis[i] * sz[i];cout << ans << "\n";return 0;
}
\(\text{luogu-2294}\)
刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了 \(n\) 个月以来的收入情况，其中第 \(i\) 个月的收入额为 \(a_i\)，\(i=1,2,\ldots,n-1,n\)。当 \(a_i>0\) 时表示这个月盈利 \(a_i\) 元，当 \(a_i<0\) 时表示这个月亏损 \(|a_i|\) 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。
刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。
现在，姹总共偷看了 \(m\) 次账本，得到 \(s,t,w\)，表示第 \(s\) 个月到第 \(t\) 个月共收入 \(w\)，你的任务是根据记住的这些信息来判断账本是不是假的。
\(1 \le T, n < 100\)，\(1 \le m < 1000\)。
显然可以用差分约束做，每个限制表示 \(x_t - x_{s-1} = w\)，于是可以建边：
跑 spfa 即可。
但是注意，由于建边的编号范围是 \(0 \sim n\)，因此超级源点不能是 \(0\)，可以让 \(n+1\) 作为超级源点。
注意：多测清空！vis 也要清空，因为提前 return 了！！
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 1005
#define pii pair<long long, long long>
#define fi first
#define se secondlong long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}long long T, n, m, dis[MAXN], cnt[MAXN];
vector<pii > v[MAXN];
bool vis[MAXN];bool spfa(long long s) {memset(dis, 0x3f, sizeof dis);memset(cnt, 0, sizeof cnt);memset(vis, 0, sizeof vis);queue<long long> q; q.push(s);dis[s] = 0, vis[s] = 1;while(!q.empty()) {long long x = q.front(); q.pop();vis[x] = 0;for(auto it : v[x]) {long long y = it.fi, w = it.se;if(dis[y] > dis[x] + w) {dis[y] = dis[x] + w, cnt[y] = cnt[x] + 1;if(cnt[y] > n + 1) return 1;if(!vis[y]) q.push(y), vis[y] = 1;}}}return 0;
}int main() {T = read();while(T --) {n = read(), m = read();for(int i = 0; i <= n + 1; i ++) v[i].clear();for(int i = 1; i <= n; i ++) v[n + 1].push_back({i, 0});for(int i = 1; i <= m; i ++) {long long x = read() - 1, y = read(), w = read();v[x].push_back({y, w}), v[y].push_back({x, -w});} if(spfa(n + 1)) cout << "false\n";else cout << "true\n";}return 0;
}
\(\text{luogu-4926}\)
今天 Scarlet 在机房有幸目睹了一场别开生面的 OI 训练。因为一些奇妙的 SPJ，比赛中所有选手的得分都是正实数（甚至没有上限）。
当一位选手 A 的分数不小于选手 B 的分数 \(k\)（\(k>0\)）倍时，我们称选手 A \(k\) 倍杀了选手 B，选手 B 被选手 A \(k\) 倍杀了。
更奇妙也更激动人心的是，训练前有不少选手立下了诸如 “我没 \(k\) 倍杀选手 X，我就吃顿好的”，“选手 Y 把我 \(k\) 倍杀，我就吃顿好的” 的 Flag。
知道真相的良心教练 Patchouli 为了维持机房秩序，避免吃的太好导致身体健康程度下滑，放宽了选手们的 Flag 限制。Patchouli 设定了一个正常数 \(T\)，立下 “我没 \(k\) 倍杀选手 X 就吃顿好的” 的选手只要成功 \(k - T\) 倍杀了选手 X，就不需要吃顿好的。同样的，立下 “选手 Y 把我 \(k\) 倍杀我就吃顿好的” 的选手只要没有成功被选手 Y \(k+T\) 倍杀，也不需要吃顿好的。
提前知道了某些选手分数和具体 Flag 的 Scarlet 实在不忍心看到这么一次精彩比赛却没人吃顿好的，为了方便和 Patchouli 交易，Scarlet 想要确定最大的实数 \(T\) 使得赛后一定有选手收 Flag 吃顿好的。
\(1\leq n,s\leq 1000\)，\(1\leq A,B,C,t\leq n\)，\(1\leq k\leq 10\)，\(1\leq x\leq 10^9\)。保证输入中的 \(C\) 两两不同。
原题可化为，给出一系列不等式：
以及一些 \(x_i\) 的值，求出最大的 \(t\) 使得不等式无解。
首先对不等式进行拆分化简：
由于有精度范围，\(>\) 可视为 \(\ge\) 操作。
根据差分约束系统连边。无解情况仅当 \(t=0\) 时不等式仍旧有解。
有解则二分求出 \(T\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 1005
#define eps 1e-12
#define pii pair<long long, double>
#define fi first
#define se secondlong long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}double res = -1, l = 1e-6, r = 1e9, b[MAXN], dis[MAXN];
struct node { long long op, x, y; double w; } a[MAXN];
long long n, m, k, cnt[MAXN];
vector<pii > v[MAXN];
bool vis[MAXN];bool spfa(double t) {for(int i = 0; i <= n; i ++) v[i].clear();for(int i = 1; i <= m; i ++)if(a[i].op == 1) v[a[i].y].push_back({a[i].x, a[i].w - t});else v[a[i].y].push_back({a[i].x, 1.0 / (a[i].w + t)});for(int i = 1; i <= n; i ++) if(b[i]) v[0].push_back({i, b[i]}), v[i].push_back({0, 1.0 / b[i]});memset(vis, 0, sizeof vis);memset(cnt, 0, sizeof cnt);queue<long long> q; vis[0] = cnt[0] = 1;for(int i = 0; i <= n; i ++) dis[i] = 1, q.push(i);while(!q.empty()) {long long x = q.front(); q.pop();vis[x] = 0;for(auto it : v[x]) {long long y = it.fi;if(dis[y] < dis[x] * it.se) {dis[y] = dis[x] * it.se, cnt[y] = cnt[x] + 1;if(cnt[y] > n + 1) return 1;if(!vis[y]) q.push(y), vis[y] = 1;}}}return 0;
}int main() {n = read(), m = read(), k = read();for(int i = 1; i <= m; i ++) {a[i].op = read(), a[i].x = read();a[i].y = read(), a[i].w = read();if(a[i].op == 1) r = min(r, a[i].w);}for(int i = 1; i <= k; i ++) {long long x = read(), y = read();b[x] = y;}while(r - l >= eps) {double mid = (l + r) / 2.0;if(spfa(mid)) res = l = mid;else r = mid;}if(res < 1e-4) cout << "-1\n";else printf("%.10lf\n", res);return 0;
}
\(\text{luogu-5590}\)
给定一张 \(n\) 个点 \(m\) 条边的有向图，构造有权图满足 \(w_i \in [1,9]\)，且 \(1 \to n\) 的所有路径权值和相等。
\(n \leq 1000\)，\(m \leq 2000\)。保证数据中不会出现重边，自环。
其实这道题不应该从权值和相等入手，会发现不太好分析。
考虑刻画这个构造边权的过程，对于每条边 \((u,v)\)，都有 \(dis_u+w_{u,v} = dis_v\)。
这里 \(dis_x\) 表示 \(1 \to x\) 的路径权值和，实际上是最短的，但这里不太重要。
考虑到这就会发现，如果原图中存在环，那么一定无解，不过前提是这个环在 \(1 \to n\) 的路径上。如果这个环和 \(1 \to n\) 的路径互不影响的话，其实也不影响有解性。
那么我们现在只考虑不存在环的情况。
会发现 \(w_{u,v} \in [1,9]\)，也就是说 \(dis_v - dis_u \in [1, 9]\)，可以拆分成以下两个式子：
于是就变成了经典的差分约束问题。
思考一下为什么这么构造一定能满足所有路径权值和相等，其实很显然，因为 \(dis_n\) 一定是一个定值，而所有路径的权值和都等于 \(dis_n\)。
需要想一下，怎么才能更好的实现这个东西。
注意：如果原图 \(1 \to n\) 无路径需要输出 -1，注意特判！
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 2005
#define pii pair<int, int>
#define fi first
#define se secondint read() {int x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}struct node { int x, y, p; } e[MAXN];
bool px[MAXN], py[MAXN], vis[MAXN];
int n, m, dis[MAXN], cnt[MAXN];
vector<int> g[MAXN], rg[MAXN];
vector<pii > v[MAXN];void dfs1(int x) {px[x] = 1;for(auto y : g[x]) if(!px[y]) dfs1(y);return;
}void dfs2(int x) {py[x] = 1;for(auto y : rg[x]) if(!py[y]) dfs2(y);return;
}bool spfa(int s) {memset(dis, 0x3f, sizeof dis);queue<int> q; q.push(s);dis[s] = 0, vis[s] = 1;while(!q.empty()) {int x = q.front(); q.pop();vis[x] = 0;for(auto it : v[x]) {int y = it.fi, w = it.se;if(dis[y] > dis[x] + w) {dis[y] = dis[x] + w, cnt[y] = cnt[x] + 1;if(cnt[y] > n + 1) return 1;if(!vis[y]) q.push(y), vis[y] = 1;}}}return 0;
}int main() {n = read(), m = read();for(int i = 1; i <= m; i ++) {e[i].x = read(), e[i].y = read();g[e[i].x].push_back(e[i].y);rg[e[i].y].push_back(e[i].x);}dfs1(1), dfs2(n);if(!px[n]) { cout << "-1\n"; return 0; }for(int i = 1; i <= m; i ++)if(px[e[i].x] && py[e[i].y]) e[i].p = 1;for(int i = 1; i <= m; i ++) if(e[i].p)v[e[i].x].push_back({e[i].y, 9}), v[e[i].y].push_back({e[i].x, -1});for(int i = 1; i <= n; i ++) v[0].push_back({i, 0});if(spfa(0)) { cout << "-1\n"; return 0; }cout << n << " " << m << "\n";for(int i = 1; i <= m; i ++) {cout << e[i].x << " " << e[i].y << " ";if(e[i].p) cout << dis[e[i].y] - dis[e[i].x] << "\n";else cout << "1\n";}return 0;
}
\(\text{atcoder-agc036d}\)
有一个带权重的有向图，顶点编号 \(0 \sim n - 1\)。
图初始时有 \(n-1\) 条边。第 \(i\) 条边从顶点 \(i\) 指向顶点 \(i+1\)，权重为 \(0\)。
Snuke 现在将为每对 \(i,j(i \ne j)\) 添加一条新边 \(i \to j\)。如果 \(i < j\)，则边的权重为 \(-1\)，否则为 \(1\)。
Ringo 是一个男孩。图中存在负权重环（总权重为负的环）会让他难过。他将删除 Snuke 添加的一些边，以使图不再包含负权重环。删除边 \(i \to j\) 的代价为 \(a_{i,j}\)。他不能删除一开始就存在的边。
找到实现 Ringo 目标所需的最小总代价。
\(3 \le n \le 500\)，\(1 \le a_{i,j} \le 10^9\)。
以下部分题解来自于 题解 AT5147 【AGC036D Negative Cycle】 - 洛谷专栏。
考虑差分约束模型，图中不存在负环等价于存在一组合法的差分约束的解。
考虑每个节点作为一个变量，第 \(i\) 个节点对应的变量为 \(x_i\)。
因为初始的边不能删去，所以一定有 \(x_i \ge x_{i + 1}\)。
考虑令 \(q_i = x_i - x_{i + 1}\)，那么就会有 \(q_i \ge 0\)。
假设保留了一条边权为 \(-1\) 的 \(i \to j\) 的边，也就是说 \(i < j\) 的话：
- 就会有 \(x_i - 1 \ge x_j\)，即 \(x_i - x_j \ge 1\)，也就是说 \(q_i + q_{i + 1} + \cdots + q_{j - 1} \ge 1\)。
假设保留了一条边权为 \(1\) 的 \(i \to j\) 的边，也就是说 \(i > j\) 的话：
- 就会有 \(x_i + 1 \ge x_j\)，即 \(x_j - x_i \le 1\)，也就是说 \(q_j + q_{j + 1} + \cdots + q_{i - 1} \le 1\)。
反过来想，如果确定了所有的 \(q_i\)，那么每一条边就应该尽可能地保留下来，这样代价最小。
对于边权为 \(-1\) 的边，是区间和 \(\ge 1\) 才能保留，也就是说如果区间和 \(= 0\) 就必须删除。
对于边权为 \(1\) 的边，是区间和 \(\le 1\) 才能保留，也就是说如果区间和 \(\ge 2\) 就必须删除。
也就是说，对于一种 \(q\) 的取值方案，\(q_i = 0\) 的每个连续段，都对应着一系列的边权为 \(-1\) 的边的删除。
而区间和 \(\ge 2\) 的区间也对应着边权为 \(1\) 的边的删除。
显然可以发现，如果出现了 \(q_i \ge 2\)，不如把它变成 \(1\)，这样一定会变得更优（边 \(i \to (i + 1)\) 不用被删除了）。
所以只需要考虑 \(q\) 的取值为 \(\{0, 1\}\) 的情况。
然后可以发现，每个 \(0\) 的连续段就对应着一部分区间的删除，所以考虑如下 DP：
记 \(dp(i, j)\) 表示考虑到了 \(q_i\)，最后一个 \(1\) 取在了 \(q_i\)，倒数第二个 \(1\) 取在了 \(q_j\) 处的情况下，可以确定的代价的最小值。
\(dp(i, j)\) 可以从 \(dp(j, k)\) 转移而来，利用二维前缀和可以快速求出转移系数。
时间复杂度为 \(\mathcal O (n^3)\)。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 505
#define INF 0x3f3f3f3f3f3f3f3flong long read() {long long x = 0, f = 1;char c = getchar();while(c > 57 || c < 48) { if(c == 45) f = -1; c = getchar(); }while(c >= 48 && c <= 57) { x = (x << 1) + (x << 3) + (c - 48); c = getchar(); }return x * f;
}long long n, a[MAXN][MAXN], b[MAXN][MAXN], f[MAXN][MAXN], ans = INF;long long g(long long k, long long j, long long i) {return b[j + 1][i] + a[n][j] - a[n][k] - a[i][j] + a[i][k];
}int main() {n = read();for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++)if(i != j) a[i][j] = read();for(int j = 1; j <= n; j ++) for(int i = j; i >= 1; i --)b[i][j] = b[i + 1][j] + b[i][j - 1] - b[i + 1][j - 1] + a[i][j];for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++)a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];for(int i = 1; i < n; i ++) {f[i][0] = g(0, 0, i);ans = min(ans, f[i][0] + g(0, i, n));for(int j = 1; j < i; j ++) {f[i][j] = INF;for(int k = 0; k < j; k ++)f[i][j] = min(f[i][j], f[j][k] + g(k, j, i));ans = min(ans, f[i][j] + g(j, i, n));}}cout << ans << "\n";return 0;
}