差分约束总结

问题模型

求解由若干不等式限制的一组最大或最小未知数解

思想

首先我们来看看最短路的松弛操作，以\(spfa\)为例：

if(dis[v]>dis[u]+w){
    dis[v]=dis[u]+w;
    if(!inq[v]) inq[v]=0,q.push(v);
}

即当图中存在\(dis[v]>dis[u]+w?\)时，就立刻松弛使其满足\(dis[v]\le dis[u]+w?\)，所以我们可以容易得到，当一张图跑完一次最短路后，对于任意一组\(u,v?\)均满足\(dis[v]\le dis[u]+w?\)，由此我们可以联想到可以将不等式转化为图中两点，对图跑最短路，不断松弛，让图中所有节点满足不等式\(dis[v]\le dis[u]+w?\)，便就是在让所有未知数满足所有不等式，求解一次差分约束系统的解。

最短路、最长路其实均使图中所有节点满足所有不等式，但是对于差分约束系统，跑最短路能得到最大的未知数，最长路能跑到最小的未知数。这是因为，不管是最短路、最长路都是尽可能地使不等式趋向取等。比如，最短路是使不等式\(dis[v]\le dis[u]+w\)尽可能取等，在此我们可以将\(dis[u]+w\)视为一个常数\(K\)，当不等式\(dis[v]\le K\)取等时，自然\(dis[v]?\)取到最大值，所以最短路求得未知数最大，最长路求得未知数最小

例题

P3275 [SCOI2011]糖果

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXM 300005
using namespace std;
int n,k;
int head[MAXM],nxt[MAXM],vv[MAXM],ww[MAXM],tot;
long long ans;
inline void add_edge(int u, int v, int w){
    vv[++tot]=v;
    ww[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int dis[MAXM];
int cnt[MAXM];
bool inq[MAXM];
queue <int> q;
inline int read()
{
    int s=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
inline bool spfa(int s){
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=0;
        for(register int i=head[u];i;i=nxt[i]){
            int v=vv[i];
            if(dis[v]<dis[u]+ww[i]){
                dis[v]=dis[u]+ww[i];
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n+1) return 0;
                if(!inq[v]) inq[v]=1,q.push(v);
            }
        }
    }
    return 1;
}
int main()
{
    n=read(),k=read();
    bool isOK=1;
    for(int i=1;i<=k;++i){
        int x,a,b;x=read(),a=read(),b=read();
        if(x==1) add_edge(a,b,0),add_edge(b,a,0);
        else if(x==2){
            if(a==b){
                isOK=0;
                break;
            }
            add_edge(a,b,1);
        }else if(x==3){
            add_edge(b,a,0);
        }
        else if(x==4){
            if(a==b){
                isOK=0;
                break;
            }
            add_edge(b,a,1);
        }else if(x==5){
            add_edge(a,b,0);
        }
    }
    if(!isOK){
        puts("-1");
        return 0;
    }
    for(register int i=n;i>=1;--i)
        add_edge(0,i,1);
    if(spfa(0)){
        for(register int i=1;i<=n;++i)
            ans+=dis[i];
        printf("%lld", ans);
    }else puts("-1");
    return 0;
}

P1993 小K的农场

P4878 [USACO05DEC] 布局

差分约束总结

原文：https://www.cnblogs.com/santiego/p/10905482.html