差分约束模板补坑与学习

很久以前就学了差分约束，但是一直没搞懂，也懒得搞懂。今天看板子，脑补了几秒钟突然就懂了。

对于一个不等式， \(x_i - x_j \le k\), 可以变形： \(x_i \le x_j + k\) 。这跟最短路的判断是一样的。

用一张图来辅助理解：

从 \(i\) 到 \(w\) 跑最短路，首先我们满足了 \(i\) 和 \(j\) 间的关系，然后又满足了 \(j\) 和 \(w\) 间的关系，因此得到一组解。不难发现，使用最短路得到的解均为最大解。

同时，注意判断无解的情况：即存在负环，

对于最简单的这种负环情况，原始不等式为： \(x_i \le x_j - 1\) \(x_j \le x_i - 1\) 显然这时是不成立的。

最后，附上洛谷P4878,半模板的差分约束代码：

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

struct node{
  int u, v, w, next;
} t[N << 1];
int head[N];

int bian = 0;
inline void addedge(int u, int v, int w){
  t[++bian] = (node){u, v, w, head[u]}, head[u] = bian;
  return ; 
}

int n, m1, m2; 

queue <int> q; 
ll dis[N]; 
int vis[N]; 

int maxn_tmp = 0; 
void spfa(int s){
  memset(dis, 0x3f3f3f3f, sizeof(dis)); 
  memset(vis, 0, sizeof(vis)); 
  maxn_tmp = dis[0]; 
  q.push(s); 
  dis[s] = 0;
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int i = head[u]; i; i = t[i].next){
      int v = t[i].v; 
      if(dis[v] > dis[u] + t[i].w){
        dis[v] = dis[u] + t[i].w; 
        vis[v]++; 
        if(vis[v] > n){
          printf("-1");
          exit(0); 
        }
        q.push(v); 
      }
    }
  }
  return ; 
}

bool in[N]; 

int main(){
  // freopen("hh.txt", "r", stdin); 
  read(n), read(m1), read(m2);
  for(int i = 1; i <= m1; i++){
    int x, y, w; 
    read(x), read(y), read(w);
    addedge(x, y, w); 
    in[x] = 1, in[y] = 1; 
  }
  for(int i = 1; i <= m2; i++){
    int x, y, w; 
    read(x), read(y), read(w); 
    addedge(y, x, -w); 
  }
  for(int i = 1; i <= n; i++)
    addedge(0, i, 0), addedge(i + 1, i, 0);    // 隐藏条件：后面一个点不能跑到前面这个点的前面去

  spfa(0); 
  spfa(1); 
  if(dis[n] == maxn_tmp || !in[n]) printf("-2\n");
  else cout << dis[n] << endl; 
  return 0;
}