差分约束题解
题目链接：【模板】差分约束 - 洛谷
注意点：
注意这一题不能用Dij，只能用SPFA 因为这样子才可以得出这个不等式组是否会无解（判断是不是有环），而且可以处理有负边的情况
思路：
差分约束： 就是下面的不等式 x1 - x2 <= c 我们转化一下，将x2移至右边🤨🤔 x1 <= c + x2 大家来观察一下这两个式子是不是非常像？😶😶 x1 <= c + x2 <==> dis(v) <= w + dis(u)😲 右边这个式子是什么？？？？？？？？？ 答：图中求最短路径！！！！！
在文章开头我们就讲了：用SPFA
这里我们就来讲解一下SPFA和Dij的不同点
SPFA和Dij的不同点：
Dij:
vis数组：标记的是这个点是否被访问过，如果这个点被访问过，就要跳过 que：使用的是一个优先队列，存的是一个pair<int, int>这个整数对，表示的是< - 距离, 点号> 注意这里距离的前面有一个负号 原因是：优先队列默认大根堆，也就是说堆顶的数据 >= 孩子的数据，但是我们要求的是最短距离，我们要的是最短的，因此我们可以在距离前面填一个负号，这样子大的距离就 < 小的距离了， 堆顶是最短的距离了
SPFA:
vis数组：标记的是这个点目前在不在队列，如果在队列，就要跳过 que：使用的是一个普通队列，存的是一个int，其中表示的是待更新出边的点 num数组：存的是经过边的条数，因为如果经过的边数 >= 点的数目，则存在负环
到这里你应该也知道，其实差分约束的代码和SPFA根本差不了多少
但是差分约束有一个重要的地方：
差分约束要求要有一个点能到其他所有点（这样子才能解出所有解） 但是图中并不一定有这个点----->因此我们需要自己建立一个点，使得它到其他所有点都有路径 但是又不能影响这个图的最短路径------>我们可以建立0号节点，并使它和所有点都有边，且到所有边的权值为0
好的，到这里我们就可以写代码了~
AC代码：
const int N = 5e3 + 5; const int M = 5e3 + 5;
int head[N];
int cnt;
int vis[N];
int dis[N];
int num[N];//存的是经过边的条数
int n, m;
struct EDGE
{
int v;
int w;
int next;
}EDGE[M + N/*注意要加N，因为0号还连接了到所有点的边*/];
void add(int u, int v, int w) {
cnt++;
EDGE[cnt].v = v;
EDGE[cnt].w = w;
EDGE[cnt].next = head[u];
head[u] = cnt;
}
bool SPFA(int s) {
queue<int>que;
memset(dis, 0x3f3f3f, sizeof(dis));
dis[s] = 0;
//memset(vis, 0, sizeof(vis));//因为没有多组输入，这个就不是必要的
que.push(s);
vis[s] = 1;
while (!que.empty())
{
int dian = que.front();
que.pop();
vis[dian] = 0;
for (int i = head[dian]; i; i = EDGE[i].next)
{
int t = EDGE[i].v;
int w = EDGE[i].w;
if (dis[t] > dis[dian] + w)
{
dis[t] = dis[dian] + w;
num[t] = num[dian] + 1;// 通过上一个点来更新该点Num的值
if (num[t] > n/**/)//因为边的条数不能超过 点数 - 1 （这里有n + 1个点）
{
return false;
}
if (vis[t] != 1)
{
vis[t] = 1;
que.push(t);
}
}
}
}
return true;
}
void solve() {
cin >> n >> m;
int u, v, c;
while (m--)
{
cin >> v >> u >> c;
add(u, v, c);
}
for (int i = 1; i <= n; i++)
add(0, i, 0);
if (SPFA(0))
{
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
}
else
{
cout << "NO" << endl;
}
}
int main() {
solve();
return 0;
}扩展：
每个人的SPFA的写法不一样
有些人是： num数组存经过边的条数 这个写法就是当num >= n时，就有负环（因为证明了点在一直更新，因为负数会使得最短距离不断变小）
有些人是： num数组存经过点的个数 这个写法就是当num >= n + 1时，就有负环（因为证明了点在一直更新，因为负数会使得最短距离不断变小）
注意两者的区别
上面我给出的是Num存的是经过边的条数的情况，下面的代码则是存经过点的个数的情况
const int N = 5e3 + 5;
const int M = 5e3 + 5;
int head[N];
int cnt;
int vis[N];
int dis[N];
int num[N];//记录的是经过的点的数目
int n, m;
struct EDGE
{
int v;
int w;
int next;
}EDGE[M + N/*注意要加N，因为0号还连接了到所有点的边*/];
void add(int u, int v, int w) {
cnt++;
EDGE[cnt].v = v;
EDGE[cnt].w = w;
EDGE[cnt].next = head[u];
head[u] = cnt;
}
bool SPFA(int s) {
queue<int>que;
memset(dis, 0x3f3f3f, sizeof(dis));
dis[s] = 0;
//memset(vis, 0, sizeof(vis));
que.push(s);
vis[s] = 1;
num[s]++;//注意这里的不同点，因为是点的个数，起点也是一个点，所以要++
while (!que.empty())
{
int dian = que.front();
que.pop();
vis[dian] = 0;
for (int i = head[dian]; i; i = EDGE[i].next)
{
int t = EDGE[i].v;
int w = EDGE[i].w;
if (dis[t] > dis[dian] + w)
{
dis[t] = dis[dian] + w;
num[t]++;
//这里并不是像num存边的条数一样是根据起点来改变num[t]的值的，而是num[t]自增++，因为这样子才是记录经过这个点的次数
if (num[t] >= n + 1/**/)//注意这里是>= n + 1,因为点的个数是n + 1,SPFA中经过一个点的次数 >= 点的个数 时，就存在负环
{
return false;
}
if (vis[t] != 1)
{
vis[t] = 1;
que.push(t);
}
}
}
}
return true;
}
void solve() {
cin >> n >> m;
int u, v, c;
while (m--)
{
cin >> v >> u >> c;
add(u, v, c);
}
for (int i = 1; i <= n; i++)
add(0, i, 0);
if (SPFA(0))
{
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
}
else
{
cout << "NO" << endl;
}
}
int main() {
solve();
return 0;
}完结撒花~~
腾讯云开发者
