「Note」2022-06-28-差分约束

属于是补写前天的遗留物。。。

$\mathbb{Problem \ Description}$

差分约束系统是一种特殊的 $n$ 元一次不等式组。包含 $n$ 个变量和 $m$ 个不等式组。每个不等式形如: $x_i - x_j \le c_k$，其中 $1 \le i, j \le n, 1 \le k \le m$ 。
问题是要求一组 $x$ 的解满足所有不等式条件，或判定无解。

$\mathbb{Algorithm}$

联系最短路中的三角形不等式 $\mathrm{dist_v \le dist_u} + w$，对于每一组约束条件，移项得到 $x_i \le x_j + c_k$，那么就连边从 $j$ 向 $i$ 连一条有向的边，边权为 $c_k$。

因为是差分作为约束，所以所有的变量同加同减是依然符合要求的。
若规避负数解，则从 $0(st)$ 向所有点连一条权值为 $0$ 的边。如果在跑最短路时，图中出现了负环，则可以判定为无解。若有解，则 $x_i = \mathrm{dist}_i$ 。

最短路算法用 $spfa$，若存在负环，则最坏时间复杂度为 $\Theta(nm)$ 。
多数时候如果有负环，最好用 $dfs$ 实现的 $spfa$。

$\mathbb{Spfa \ Code}$

dfs版本

bool dfs_spfa(int u) {
	vis[u] = true;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v, w = G[u][i].w;
		if (dis[v] > dis[u] + w) {
			dis[v] = dis[u] + w;
			if (vis[v] || !dfs_spfa(v)) return false;
		}
	}
	vis[u] = false;
	return true;
}

bfs版本

bool bfs_spfa(int st) {

	memset(vis, 0, sizeof(vis));
	memset(dis, 0xcf, sizeof(dis));
	while (!que.empty()) que.pop();
	que.push(st), dis[st] = 0;

	while (!que.empty()) {
		int u = que.front(); que.pop();
		vis[u] = 0, cnt[u]++;
		if (cnt[u] == n) return false;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].v, w = G[u][i].w;
			if (dis[v] >= dis[u] + w) continue;
			dis[v] = dis[u] + w;
			if (!vis[v]) vis[v] = 1, que.push(v);
		}
	}

	return true;

}

</deitails>