差分约束

用途：
(1)求不等式组的可行解
源点需要满足的条件：从源点出发，一定可以遍历所有的边。
(到所有边不等价与到所有点，因为可能有孤立点)

步骤：
[1]先将每个不等式x[i] <= x[j] + c[k],转化成一条从x[j]走到x[i],长度为c[k]的一条边；
[2]找一个源点，使得该源点一定可以遍历到所有边；
[3]选任意一个点为源点求一遍单源最短路
    结果1：如果存在负环，则原不等式组一定无解；
    结果2：如果没有负环，则dist[i]就是原不等式组的一组可行解

(2)如何求可行解中的最大值或最小值，这里的最值指的是对于每个变量来说。
结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路。
问题：如何转换x[i] <= c , 其中c是一个常数。
方法：建立一个虚拟源点0，然后建立0->i，长度是c的边即可。(这就相当于求出所有可行解中的交集)
以求x[i]的最大值为例：求所有从x[i]出发，构成的不等式链x[i]<=x[j]+c[1]<=x[k]+c[2]+c[1]<=…<=c+c[1]+c[2]+…
所计算出的上界，最终x[i]的最大值等于所有上界的最小值。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

typedef long long LL;

const int N = 100010 , M = 3 * N;

int e[M] , ne[M] , w[M] , h[N] , idx;
LL dist[N];
int cnt[N];//记录更新了几次
bool st[N];
int n , m;

void add(int a , int b , int c)
{
    e[idx] = b , ne[idx] = h[a] , w[idx] = c , h[a] = idx++;
}

bool spfa()
{
    stack<int> q;
    q.push(0);
    memset(dist , -0x3f , sizeof dist);//因为求的是最长路，所以初始化负无穷
    dist[0] = 0;
    st[0] = true;

    while(q.size())
    {
        int t = q.top();
        q.pop();
        st[t] = false;

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n + 1) return false;//加入了虚拟源点所以，除了自己一共有n个节点，当更新了n+1次说明有正环
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return true;
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);
    while(m--)
    {
        int a , b , x;
        cin >> x >> a >> b;
        if(x == 1) add(a , b , 0) , add(b , a , 0);
        else if(x == 2) add(a , b , 1);
        else if(x == 3) add(b , a , 0);
        else if(x == 4) add(b , a , 1);
        else add(a , b , 0);
    }

    for(int i = 1 ; i <= n ; i++) add(0 , i , 1);//从虚拟源点向每个节点连一条长度是1的边

    if(!spfa())  cout << -1 << endl;
    else
    {
        LL res = 0;
        for(int i = 1 ; i <= n ; i++) res += dist[i];
        cout << res << endl;
    }

    return 0;
}