1. 差分约束

1.1. 介绍

差分约束算法用于解决如下问题：给出若干形如 \(x_a-x_b\le c\) （均为整数，可以为负数）的不等式，求一组解 \(\{x_i\}\)，若不存在解则判断无解。

考虑将原式变形，变为 \(x_a\le x_b+c\)。观察到这与单源最短路里的三角形不等式 \(dis_a\le dis_b+w\) （\(w\) 为节点 \(a,b\) 之间的某边边权）相似。我们使 \(x_i\) 为从源点到节点 \(i\) 的最短路径，对于不等式 \(x_a\le x_b+c\) 我们从节点 \(b\) 向节点 \(a\) 连一条边权为 \(c\) 的有向边。特殊地，我们建立一个源点 \(0\)，从源点向所有节点连一条边权为 \(0\) 的有向边，并以源点作为最短路起点。

我们一般采用 SPFA 进行最短路，若图中存在负环，则差分约束系统无解。
特殊地，有些题也可转化为最长路形式进行拓扑排序，因题而异。

1.2. 常见技巧

1.2.1 常见变形

原式	变形	建边
\(x_a-x_b\le c\)	\(x_a\le x_b+c\)	`add(b,a,c)`
\(x_a-x_b\ge c\)	\(x_b\le x_a-c\)	`add(a,b,-c)`
\(x_a-x_b<c\)	\(x_a\le x_b+c-1\)	`add(b,a,c-1)`
\(x_a-x_b>c\)	\(x_b\le x_a-c-1\)	`add(a,b,-c-1)`
\(x_a=x_b\)	\(x_a-x_b\le0,x_b-x_a\le0\)	`add(a,b,0),add(b,a,0)`

1.2.2 简单性质

显著的，将我们得出的一组解 \(x_i\) 整体加减一个常量不影响正确性，因为都消掉了。

1.3 题目

\(\color{limegreen}{P5960\ 【模板】差分约束算法}\)

模板题。

\(\text{Code:}\)

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=1e5+2,M=1e5+2;

int n,m;
//----------//
//Edge
struct Edge
{
    int to,w,nex;
}edge[M];
int tot,head[N];
void add(int from,int to,int w)
{
    edge[++tot].nex=head[from];
    head[from]=tot;
    edge[tot].to=to;
    edge[tot].w=w;
    return;
}
//--------------------//
//SPFA
bool vq[N];
int v[N],dis[N];
queue<int>q;
void SPFA(int st)
{
    //printf("ST:%d\n",st);
    memset(v,0,sizeof(v));
    memset(vq,0,sizeof(vq));
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    vq[st]=true;
    q.push(st);
    while(!q.empty())
    {
        int now=q.front();
        //printf("now:%d\n",now);
        q.pop();
        vq[now]=false,v[now]++;
        if(v[now]>n)
            printf("NO"),exit(0);
        for(int to,w,i=head[now];i;i=edge[i].nex)
        {
            to=edge[i].to,w=edge[i].w;
            //printf("to:%d %d %d\n",to,dis[to],dis[now]+w);
            if(dis[now]+w<dis[to])
            {
                dis[to]=dis[now]+w;
                //printf("%d %d %d\n",dis[to],dis[now],w);
                if(!vq[to])
                    q.push(to),vq[to]=true;
            }
        }
    }
}
//-------------------//
int main()
{
    scanf("%d%d",&n,&m);
    for(int from,to,w,i=1;i<=m;i++)
    {
        scanf("%d%d%d",&to,&from,&w);
        add(from,to,w);
    }
    for(int i=1;i<=n;i++)
        add(n+1,i,0);
    SPFA(n+1);
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x3f3f3f3f)
            dis[i]=0;
        printf("%d ",dis[i]);
    }
    return 0;
}

\(\color{royalblue}{P3275 [SCOI2011] 糖果}\)

将不等式列出之后注意转化、建边细节，这道题用 SPFA 会被卡，需要转化为最长路用拓扑排序求解。

\(\text{Code:}\)

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=2e5+1,M=5e5+1;

int n,k;
//--------------------//
//Graph
struct Edge
{
    int to,w,nex;
}edge[M][2];
int tot[2],head[N][2];
void add(int from,int to,int w,int op)
{
    edge[++tot[op]][op]={to,w,head[from][op]};
    head[from][op]=tot[op];
    return;
}
struct Poi
{
    int dfn,low;
}p[N];
//----------//
//Tarjan
int dcnt;
int stcnt,sta[N];
bool sv[N];
int scnt,scc[N],sc[N],in[N];
void Tarjan(int now,int fa)
{
    dcnt++,p[now]={dcnt,dcnt},sta[++stcnt]=now,sv[now]=true;
    for(int to,i=head[now][0];i;i=edge[i][0].nex)
    {
        to=edge[i][0].to;
        if(!p[to].dfn)
            Tarjan(to,now),p[now].low=min(p[now].low,p[to].low);
        else if(sv[to])
            p[now].low=min(p[now].low,p[to].dfn);
    }
    if(p[now].dfn==p[now].low)
    {
        scnt++;
        while(sta[stcnt]!=now)
        {
            scc[sta[stcnt]]=scnt;
            sv[sta[stcnt]]=false;
            stcnt--;
            sc[scnt]++;
        }
        scc[sta[stcnt]]=scnt;
        sv[sta[stcnt]]=false;
        stcnt--;
        sc[scnt]++;
    }
    return;
}
//--------------------//
LL f[N];
queue<int>q;
void BFS()
{
    for(int i=1;i<=scnt;i++)
        if(!in[i])
            f[i]=1,q.push(i);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int to,w,i=head[now][1];i;i=edge[i][1].nex)
        {
            to=edge[i][1].to,w=edge[i][1].w;
            f[to]=max(f[to],f[now]+w);
            in[to]--;
            if(!in[to])
                q.push(to);
        }
    }
    return;
}
//--------------------//
int main()
{
    scanf("%d%d",&n,&k);
    for(int op,x,y,i=1;i<=k;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        switch(op)
        {
            case 1:
                add(x,y,0,0),add(y,x,0,0);
                break;
            case 2:
                add(x,y,1,0);
                break;
            case 3:
                add(y,x,0,0);
                break;
            case 4:
                add(y,x,1,0);
                break;
            case 5:
                add(x,y,0,0);
                break;
        }
    }
    for(int i=1;i<=n;i++)
        if(!p[i].dfn)
            Tarjan(i,0);
    for(int i=1;i<=n;i++)
    {
        for(int to,w,j=head[i][0];j;j=edge[j][0].nex)
        {
            to=edge[j][0].to,w=edge[j][0].w;
            if(w&&scc[i]==scc[to])
            {
                printf("-1");
                return 0;
            }
            else if(scc[i]!=scc[to])
                add(scc[i],scc[to],w,1),in[scc[to]]++;
        }
    }
    BFS();
    LL ans=0;
    for(int i=1;i<=scnt;i++)
        ans+=1LL*f[i]*sc[i];//printf("%d %d %d\n",f[i],sc[i],in[i]);
    printf("%lld",ans);
    return 0;
}