差分约束专题

• P5960 差分约束算法

显然题。

首先有 $x_{c1}-x_{c1’} \le y_1$。
那么有 $x_{c1} \le x_{c1’} + y_1$。
所以看到图论里面的松弛操作，即最终使得 dist[to]<=dist[cur]+e[i].val。

要使得这个成立所以要跑一遍最短路。

那么将 $x$ 视为 dist，c1 视为 to，c1' 视为 cur 即可。

然后因为跑最短路的 dijkstra 需要源点，即单源最短路径。
所以直接造一个源点就可以跑了，并没有什么实际作用（

判负环似乎只需要加上一个统计入队次数的 cnt 即可。
因为显然，有负环就没有合法解。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 10;
int n, m, cnt; bool inq[N];
int head[N<<1], dist[N], vis[N];

struct Edge {
  int to, nxt, val;
} e[N<<1];

void addEdge(int u, int v, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].val = w; head[u] = cnt;
  return ;
}

bool spfa() {
  queue <int> sp; sp.push(0);
  vis[0] = 1, inq[0] = true;
  memset(dist, 0x3f, sizeof dist);
  dist[0] = 0;
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (dist[to] > dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) {
          inq[to] = true, sp.push(to);
          ++vis[to]; if (vis[to]>n) return true;
        }
      }
    }
  }
  return false;
}

int main() {
  memset(head, -1, sizeof head);
  cin >> n >> m;
  for (int i=1; i<=m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    addEdge(v, u, w);
  }
  for (int i=1; i<=n; ++i) addEdge(0, i, 0);
  if (spfa()) { puts("NO"); return 0; }
  for (int i=1; i<=n; ++i) cout << dist[i] << ' ';
  return 0;
}