发布时间：2024-07-31

差分约束

求不等式组的可行解
求最大最小值

求不等式组的可行解

对于最短路的每次更新 $ dis_v<=dis_u+c $ ,因此可以类比为形如$ x_i<=x_j+c $ 的不等式组，其中 $ x_i,x_j $ 为自变量,$ c $为常数

先将每个不等式组转化为边
找一个虚拟源点，可以遍历所有边
从源点求单源最短路
若有负环，则原不等式组无解；否则$ dis_i $ 为可行解

求最大最小值(每个变量的最大最小值)

求最大值，则求最短路
求最小值，则求最长路
对于一个确定的$ i $都可以放缩成若干个 $ x_i<=x+c $ 的形式，一定存在一个不等式 $ x_i<=c即x=0(源点) $ ,否则所有都是相对关系不可能有最值
- 求最大值为例
- $ x_i<=x_j+c_1<=x_k+c_1+c_2<=... $
- 最大值即为每个上界的最小值
- 建立一个虚拟源点0,有0->i权值为c的边
- 所有点的最大上界都等于它到源点的边长，因此使用最短路求解，$ dis_i $ 即为每个点的最大值

总结：

建立关系
找出虚拟源点
求最长路最短路,判环是否有解

模板

如果 $X=1$ ，表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；
如果 $X=2$ ，表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；
如果 $X=3$ ，表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；
如果 $X=4$ ，表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；
如果 $X=5$ ，表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果；

最小值，即求最长路
$ x=1:A>=B,B>=A $
$ x=2:B>=A+1 $
$ x=3:A>=B $
$ x=4:A>=B+1 $
$ x=5:B>=A $
虚拟源点：$ 所有人糖果大于等于1:x>=0+1 $

cpp

vector<vector<array<int,2>>> adj;
int n,k;
vector<int> dis,cnt;
vector<bool> st;
bool spfa(){
    for(int i=1;i<=n;i++)dis[i]=-1e13;
    dis[0]=0;
    int tt=-1,hh=0;
    queue<int> q;
    q.push(0);
    st[0]=1;
    int count=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        st[u]=0;
        for(auto [v,c]:adj[u]){
            if(dis[v]<dis[u]+c){
                dis[v]=dis[u]+c;
                cnt[v]=cnt[u]+1;
                if(++count>=1e6)return false;
                if(cnt[v]>=n+1)return false;
                if(!st[v]){
                    q.push(v);
                    st[v]=1;
                }
            }
        }
    }
    return true;
}
void solve(){
    cin>>n>>k;
    adj=vector<vector<array<int,2>>> (n+1);
    dis=vector<int>(n+1);
    cnt=vector<int>(n+1);
    st=vector<bool>(n+1);
    while(k--){
        int x,u,v;
        cin>>x>>u>>v;
        if(x==1){
            adj[u].push_back({v,0});
            adj[v].push_back({u,0});
        }
        else if(x==2){
            adj[u].push_back({v,1});
        }
        else if(x==3){
            adj[v].push_back({u,0});
        }
        else if(x==4){
            adj[v].push_back({u,1});
        }
        else{
            adj[u].push_back({v,0});
        }
    }
    for(int i=1;i<=n;i++)adj[0].push_back({i,1});
    if(!spfa())puts("-1");
    else{
        int ans=0;
        for(int i=1;i<=n;i++)ans+=dis[i];
        cout<<ans<<"\n";
    }
}

差分约束 ​

差分约束