差分约束系统

差分约束的定义：

　　差分约束系统是一种特殊的一元一次不等式组，约束条件就是一些以两个变量做差的形式构成，形如X_i-X_j<=C_k（C_k为常数，是一个已知的量），

　　我们所需要求一组解，使得所有的约束条件的不等式都得到满足。

　　将差分约束的条件进行移项变形可以得到：Xi<=X_j+ C_k，仔细观察可以发现这个式子与求单源最短路中的不等式 dis[v]<=dis[u]+p[i].val非常相似，

　　因此可以把每个变量X_i 看成图中的一个结点i,对于每个约束条件Xi-Xj<=Ck，由结点j向结点i连一条权值为Ck的有向边，

　　至于为什么是由结点j连向结点i而不是结点i连向结点j的原因是在必须要满足Xi<=X_j+ C_k，而在跑最短路的时候只有在dis[v]>=dis[u]+p[i].val的时候才会更新dis[v]=dis[u]+p[i].val,这样才满足了dis[v]<=dis{u]+p[i].val的条件，且最短路中是u向v连有向边，所以这里也是j向i连有向边。

　　在平常的题目有些约束条件并不是这样的，但我们可以通过适量的变形来达到这样的效果，比如说条件为：X_i-X_j>=C_k，

　　此时我们仍然看成j向i连长为C_k的有向边，只是由跑单源最短路改成跑单源最长路而已，或者将不等式两边同是乘以-1并移项，将式子变为X_j-X_i<= -C_k后，再跑最短路。

习题：

L1250 种树：https://www.luogu.org/problemnew/show/P1250

解题思路：

　　差分约束的板子题。。。

　　设dis[i]表示[1,i]之间一共种了dis[i]颗树，所以有：dis[y]-dis[x-1]>=z,dis[y]>=dis[x-1]+z,由x-1向y建一条权值为z的有向边,转化为跑最长路。

但是题目中也有隐含条件：每个部分最多能种1棵树，所以有:

①：dis[i]-dis[i-1]<=1 dis[i-1]-dis[i]>=-1

②：dis[i]-dis[i-1]>=0

成功建完图后跑一遍最长路就行啦。

#include<bits/stdc++.h>
using namespace std;
#define maxn 30009
struct edge
{
    int to,nxt,val;
}p[maxn*3];
int head[maxn],dis[maxn];
queue<int>q;
int n,m,k,ans,tot,cnt;
bool vis[maxn];

void add(int x,int y,int z)
{
    ++cnt;
    p[cnt].to=y;
    p[cnt].nxt=head[x];
    p[cnt].val=z;
    head[x]=cnt;
 } 
void Spfa()
{
    memset(dis,-1,sizeof(dis));
    dis[0]=0;
    vis[0]=1;
    q.push(0);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=p[i].nxt)
        {
            int v=p[i].to;
            if(dis[v]<dis[u]+p[i].val)
            {
                dis[v]=dis[u]+p[i].val;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        add(i,i+1,0);
    for(int i=1;i<=n;i++)
        add(i,i-1,-1);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x-1,y,z);
    }
    Spfa();
    printf("%d
",dis[n]);
    return 0;
}

View Code

#10087. 「一本通 3.4 例 1」Intervals：https://loj.ac/problem/10087

解题思路：

　　和上一题思路一样。

　　设dis[i]表示从[0,i]内最少选出dis[i]个数，由题意可得：dis[b]-dis[a-1]>=C,由此可以将其转换为差分约束的模型。

　　但是题目中仍然有有一些较隐含的条件：

　　①：dis[i]-dis[i-1]>=0 ，0到i之间选出的数肯定要比0到i-1之间选出的数多

　　②：dis[i]-dis[i-1]<=1 ，由于每个数至多只能选一次，所以差值一定要小于等于1，将其变形为dis[i-1]-dis[i]>=-1。

　　最后把所有整数作为图中结点并适当连边跑单源最短路就行了。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 50009
#define maxm
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}
struct edge
{
    int to,nxt,val;
}p[maxn];
bool vis[maxn];
int dis[maxn],head[maxn];
int n,m,k,ans,tot,cnt,sum,mx,mn=INF; 
void add(int x,int y,int z)
{
    ++cnt,p[cnt].to=y,p[cnt].nxt=head[x],p[cnt].val=z,head[x]=cnt;
}
void Spfa(int s)
{
    for(int i=mn;i<=mx;i++)
        dis[i]=-INF;
    dis[s]=0,vis[s]=1;
    queue<int>q;
    q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
    //    cout<<"nice "<<u<<endl;
        for(int i=head[u];i;i=p[i].nxt)
        {
            int v=p[i].to;
            if(dis[v]<dis[u]+p[i].val)
            {
                dis[v]=dis[u]+p[i].val;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
         } 
         vis[u]=0;
    }
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)//由于0也是一个结点，但连边的时候需要用到i-1，当i==0时下标出现负数，所以直接将没个整数加1，避免负数下标 
    {
        int x=read(),y=read(),k=read();++x,++y;
        mx=max(mx,y),mn=min(mn,x-1);
        add(x-1,y,k);
    }
//    cout<<"ok "<<mn<<" "<<mx<<endl;
    for(int i=mn;i<=mx;i++)//隐含的条件，可以保证整张图连通。 
        add(i,i+1,0),add(i+1,i,-1);
    Spfa(mn);
//    for(int i=mn;i<=mx;i++)
//        cout<<dis[i]<<" ";
//    cout<<endl; 
    printf("%d
",dis[mx]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

L2294 [HNOI2005]狡猾的商人：https://www.luogu.org/problemnew/show/P2294

解题思路：

　　列出不等式：z<=dis[y]-dis[x-1]<=z,将其拆分为两个不等式，分别建边。

①：dis[y]-dis[x-1]<=z dis[y]<=dis[x-1]+z

②：dis[y]-dis[x-1]>=z dis[x-1]<=dis[y]-z

最后跑最短路，判断是否有负环的存在。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 109
#define maxm 1009
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}
bool vis[maxn];
int head[maxn],dis[maxn];
struct edge
{
    int to,nxt,val;
}p[maxm<<2];
int n,m,k,ans,tot,cnt,T; 

void add(int x,int y,int z)
{
    p[++cnt]={y,head[x],z},head[x]=cnt;
}
bool Spfa(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].to;
        if(dis[v]>dis[u]+p[i].val)
        {
            dis[v]=dis[u]+p[i].val;
            if(vis[v]||!Spfa(v))
                return false;
        }
    }    
    vis[u]=0;
    return true;
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    T=read();
    while(T--)
    {
        memset(dis,INF,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head)),cnt=0;
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),z=read();
            add(y,x-1,-z),add(x-1,y,z);
        }
        dis[0]=0;
        if(!Spfa(0))
            puts("false");
        else
            puts("true");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

L1993 小K的农场：https://www.luogu.org/problemnew/show/P1993

解题思路：

　　做多了差分约束的题目就会发现都是套路题。。。

　　列出不等式：

①：dis[a]-dis[b]>=c

②:dis[a]-dis[b]<=c

③：0<=dis[a]-dis[b]<=0

　把以上的不等式全部转化成>=的形式，最后跑最长路判断是否有正环的存在。

还要建结点0和任意一个点的边，此时的0相当于一个超级源，为了保证图连通。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 10009
#define maxm
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}
bool vis[maxn];
int head[maxn],dis[maxn];
int n,m,k,ans,tot,cnt;
bool flag=false;
struct edge
{
    int to,nxt,val;
}p[maxn<<2];

void add(int x,int y,int z)
{
    p[++cnt]={y,head[x],z},head[x]=cnt;
}

bool Spfa(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].to;
        if(dis[v]<dis[u]+p[i].val)
        {
            dis[v]=dis[u]+p[i].val;
            if(vis[v])
                return false;
            if(!Spfa(v))
                return false;
        }
    }
    vis[u]=0;
    return true;
}

int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int opt=read(),x=read(),y=read(),z;
        if(opt==3)
        {
            add(x,y,0),add(y,x,0);
            continue;
        }
        z=read();
        if(opt==1)
            add(y,x,z);
        else
            add(x,y,-z);
    }
    for(int i=1;i<=n;i++)
        add(0,i,0),dis[i]=-INF;
    if(Spfa(0))
        puts("Yes");
    else
        puts("No");
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

L1260 工程规划：https://www.luogu.org/problemnew/show/P1260

解题思路：

　　差分约束。。。列不等式。。。

dis[x]-dis[y]<=z dis[x]<=dis[y]+z 由y向x连一条权值为z的有向边。。。

跑最短路，对于每一个没有做过的点都要做一次，最后对dis数组取min，再拿dis数组减去min就是ans了。

这样做可以保证至少有一个为0，而且为0的可能不止一个。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 1009
#define maxm 5009
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}

bool flag=true;
int head[maxn],dis[maxn],cont[maxn];
int n,m,k,ans,tot,cnt,mn=INF;
struct edge
{
    int to,nxt,val;
}p[maxm]; 

void add(int x,int y,int z)
{
    p[++cnt]={y,head[x],z},head[x]=cnt;
}

void Spfa(int s)
{
    dis[s]=0,cont[s]=1;
    queue<int>q;q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=p[i].nxt)
        {
            int v=p[i].to;
            if(dis[v]>dis[u]+p[i].val)
            {
                dis[v]=dis[u]+p[i].val;
                cont[v]++;
                if(cont[v]>n)
                {
                    puts("NO SOLUTION");
                    exit(0);
                }
                q.push(v);
            }
        }
    }
}

int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    memset(dis,INF,sizeof(dis));
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add(y,x,z);
    }
    for(int i=1;i<=n;i++)
        if(!cont[i])
            Spfa(i);
    for(int i=1;i<=n;i++)
        mn=min(mn,dis[i]);
    for(int i=1;i<=n;i++)
        printf("%d
",dis[i]-mn);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

L3275 [SCOI2011]糖果：https://www.luogu.org/problemnew/show/P3275

解题思路：

　　还是差分约束。。。

　　还是列不等式。。。

　还是跑最长路。。。

　　注意事项：输入有A=B的情况，如果矛盾直接退出就好了，最后和0建边的时候要倒序枚举，因为数据的特殊性，题解还是讨论里好像有说吧，就是一条长链的情况。。。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 100009
#define maxm
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}
bool flag=false;
int head[maxn],cont[maxn];
ll dis[maxn];
struct edge 
{
    int to,nxt;
    ll val;
}p[maxn*10];
int n,m,k,tot,cnt;
ll ans; 

void add(int x,int y,ll z)
{
    p[++cnt]={y,head[x],z},head[x]=cnt;
}

bool Spfa(int s)
{
    dis[s]=0,cont[s]=1;
    queue<int>q;q.push(s);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=p[i].nxt)
        {
            int v=p[i].to;
            if(dis[v]<dis[u]+p[i].val)
            {
                dis[v]=dis[u]+p[i].val;
                cont[v]++;
                if(cont[v]>=n)
                    return 0;
                q.push(v);
            }
        }
    }
    return 1;
}


int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int opt=read(),a=read(),b=read();
        if(opt==1)
            add(a,b,0),add(b,a,0);
        if(opt==2)
        {
            if(a==b)
            {
                puts("-1");
                return 0;    
            }
            add(a,b,1);
        }
            
        if(opt==3)
            add(b,a,0);
        if(opt==4)
        {
            if(a==b)
            {
                puts("-1");
                return 0;
            }
            add(b,a,1);
        }
        if(opt==5)
            add(a,b,0);
    }
//    for(int i=1;i<=n;i++)
//        add(0,i,1);
    for(int i=n;i>=1;i--)
        add(0,i,1);
    if(!Spfa(0))
        puts("-1");
    else
    {
        ans=0;
        for(int i=1;i<=n;i++)
            ans+=dis[i];
        printf("%lld
",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code

L4878 [USACO05DEC]layout布局：https://www.luogu.org/problemnew/show/P4878

解题思路：

　　列不等式（啊，我快疯了）：

①：dis[y]-dis[x]<=z dis[y]<=dis[x]+z

②：dis[y]-dis[x]>=z dis[x]<=dis[y]-z

跑最短路。。。

　　注意事项：这题特意卡了后3个测试点，要先从0跑一遍判断图的连通性，再从1跑一遍。

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 1009
#define maxm
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ll)(ch-'0');ch=getchar();}
    return x*f;
}
bool vis[maxn];
int head[maxn],dis[maxn];
struct edge
{
    int to,nxt,val;
}p[maxn*10*2];
int n,m,k,ans,tot,cnt;

void add(int x,int y,int z)
{
    p[++cnt]={y,head[x],z},head[x]=cnt;
}

bool Spfa(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=p[i].nxt)
    {
        int v=p[i].to;
        if(dis[v]>dis[u]+p[i].val)
        {
            dis[v]=dis[u]+p[i].val;
            if(vis[v]||!Spfa(v))
                return false;
        }
    }
    vis[u]=0;
    return true;
}
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);

    n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++)
        add(0,i,0);
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        add(x,y,z);
    }
    for(int i=1;i<=k;i++)
    {
        int x=read(),y=read(),z=read();
        add(y,x,-z);
    }    
    memset(dis,INF,sizeof(dis));
    dis[0]=0;
    if(!Spfa(0))
    {
        puts("-1");
        return 0;
    }
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
    Spfa(1);
    if(dis[n]==INF)
        puts("-2");
    else
        printf("%d
",dis[n]);    
/*    for(int i=1;i<=n;i++)
        cout<<dis[i]<<" ";
    cout<<endl;*/
    fclose(stdin);
    fclose(stdout);
    return 0;
}

View Code