本文主要是记录差分约束系统练习题的思路和代码,在此不再详细解释算法原理。

差分约束系统原理,参考文章:https://blog.csdn.net/dragon60066/article/details/80245797

POJ 1275 Cashier Employment

思路:

设 num[i] 为来应聘的在第i个小时开始工作的人数,
   r[i] 为第i个小时至少需要的人数,
   x[i] 为招到的在第i个小时开始工作的人数,
   x[i] 的前缀和为 s[i] ;
   为了防止下标出现-1,将0~23右移一位,之后用1~24表示时刻。
   根据题意有:
         0 <= x[i] <= num[i] 即 0<=s[i]-s[i-1]<=num[i]
         x[i] + x[i-1] + … + x[i-7] >= r[i] (题目中的连续工作8小时)
   则有: 
         s[i] – s[i-1] >= 0, 1 <= i <= 24
         s[i-1] – s[i] >= –num[i], 1 <= i <= 24
         s[i] – s[i-8] >= r[i], 9 <= i <= 24
         s[i] – s[i+16] >= r[i] – s[24],  1<= i <= 8 
  (s[24]就是枚举的ans,在枚举的时候把它当成已知量ans,可以写成s[i] – s[i+16] >= r[i] – ans)
   还需要添加一个隐藏不等式: s[24] – s[0] >= ans(枚举的答案)
   这样才能保证s[24]是大于等于ans的最小值。
   二分枚举s[24],题目是求最小值,即建图后以1为源点求最长路,并判断是否有负环。

AC代码:

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=30,M=1e5+10,inf=0x7f7f7f7f;
bool vis[N];
int n,cnt,r[N],head[N],dis[N],tot[N],num[N];
struct edge
{
    int to,next,w;
}e[M<<1];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
bool judge(int mid)
{
    //连边; 点下标为0~24
    cnt=0;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=24;i++)
    {
        if(i<=8)add(16+i,i,r[i]-mid);//i=8 16+i=24
        else add(i-8,i,r[i]);
        add(i,i-1,-num[i]);
        add(i-1,i,0);
    }
    add(0,24,mid);
    //SPFA 求最长路
    memset(dis,-inf,sizeof(dis));//注意初始化为-inf(别写成了inf)
    memset(tot,0,sizeof(tot));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(0);
    vis[0]=1;
    dis[0]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        if(++tot[u]>24)return 0;//判环
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]<dis[u]+e[i].w)//最长路
            {
                dis[v]=dis[u]+e[i].w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    int T,n,x;
    cin>>T;
    while(T--)
    {
        for(int i=1;i<=24;i++)//下标进行加1处理,从1开始
            cin>>r[i];
        cin>>n;
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            num[x+1]++;//输入的时刻+1
        }
        int L=0,R=n;
        int ans=-1;
        while(L<=R)//二分答案
        {
            int mid=(L+R)/2;
            if(judge(mid))ans=mid,R=mid-1;
            else L=mid+1;
        }
        if(ans==-1)printf("No Solution\n");
        else printf("%d\n",ans);
    }
    return 0;
}

洛谷 P3275 [SCOI2011]糖果

思路:

   x=1,A=B等价于A-B>=0且B-A>=0
   x=2,A<B等价于B-A>0,即B-A>=1
   x=3,A>=B等价于A-B>=0
   x=4,A>B等价于A-B>0,即A-B>=1
   x=5,A<=B等价于B-A>=0
   (A,B表示每个人得到的糖果a[]的下标)
   最后,还要求每个小朋友都要分到糖果,
   所以a[i]-a[0]>=1(1<=i<=n),则从0连到i一条边,权值为1。
   建图完成后,跑一遍最长路,如果没有负环,
   则dis[i]就是a[i]满足约束条件的一个解(而且尽量小)。最后求和dis[i]即可。

这题我写了几次,都是TLE或者RE,坑的地方在于:
1. 要特判 x=2或x=4 的时候A==B则直接输出-1,否则再跑SPFA会TLE
2. 必须逆序遍历(n到1)连边,否则TLE (此处特别玄学,SPFA的复杂度和连边顺序有关,数据卡了SPFA)
3. 把边的数组开小了,只开了1e5,然后RE(要避免这种低级错误就是先写连边的代码,算完边数之后再写数组大小)

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=3e5+10,inf=0x7f7f7f7f;
int n,m,cnt,head[N],tot[N];
ll dis[N];
bool vis[N];
struct edge
{
    int to,w,next;
}e[M];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
ll spfa()
{
    queue<int>q;
    q.push(0);
    memset(dis,0,sizeof(dis));
    dis[0]=0;
    vis[0]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        if(++tot[u]>n)return -1;//有负环
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if(dis[v]<dis[u]+w)//最长路
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)//求和
        ans+=dis[i];
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    int opt,a,b;
    for(int i=1;i<=m;i++)
    {
        cin>>opt>>a>>b;
        if(a==b&&(opt==2||opt==4)){printf("-1\n");return 0;}
        //一定要特判,否则之后SPFA超时
        if(opt==1)add(b,a,0),add(a,b,0);
        else if(opt==2)add(a,b,1);
        else if(opt==3)add(b,a,0);
        else if(opt==4)add(b,a,1);
        else if(opt==5)add(a,b,0);
    }
    for(int i=n;i>=1;i--)//必须按逆序连边,否则SPFA超时
        add(0,i,1);
    printf("%lld\n",spfa());
    return 0;
}

洛谷 P4878 [USACO05DEC]Layout G

思路:

   x,y表示位置a[]的下标,z表示权值
   (1) x-y<=z
   (2) x-y>=z => y-x<=-z
   (3) 隐含条件,位置必须按下标的顺序排列,则a[i]-a[i-1]>=0,即a[i-1]-a[i]<=0
   化成这种形式(左边未知数,右边已知数,"<="的符号连接),"<="的符号说明是跑最短路。
   从1开始跑最短路,dis[1]=0,如果有解,得到dis[n],答案为dis[n]-dis[1]=dis[n];
   怎么判断是否有解(无负环)呢?直接从1开始跑最短路就能正确判断吗?看看下面的细节分析。

细节上要注意的地方:
1. 判断是否有解,不能只跑一次SPFA。因为图不一定连通,从1开始跑SPFA,不一定能遍历到所有点,可能存在负环,但是从1开始遍历不到那个负环。为了解决这个问题,需要建一个超级源点,下标为0,把它与所有点连边,从0开始跑一遍SPFA判断是否有负环。
2. 经过SPFA(0)之后,若无负环,则再正常跑SPFA(1)。如果无法到达终点,说明dis[n]可以任意大,输出-2;否则输出dis[n]。

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e5+10,inf=0x7f7f7f7f;
int n,m1,m2,cnt,tot[N],head[N],dis[N];
bool vis[N];
struct edge
{
    int to,w,next;
}e[M];
void add(int x,int y,int z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
queue<int>q;
int spfa(int s)
{
    while(!q.empty())q.pop();
    memset(dis,inf,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(tot,0,sizeof(tot));
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        if(++tot[u]>n)return -1;
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if(dis[v]>dis[u]+w)//最短路
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if(dis[n]==inf)return -2;//遍历不到终点,dis[n]可以任意大
    return dis[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m1>>m2;
    int x,y,z;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m1;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
    }
    for(int i=1;i<=m2;i++)
    {
        cin>>x>>y>>z;
        add(y,x,-z);
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=1)add(i,i-1,0);
        add(0,i,0);
    }
    int ans=spfa(0);//先从0(超级源点)开始跑一次SPFA判断是否有负环
    if(ans==-1)printf("-1\n");//有负环
    else printf("%d\n",spfa(1));//没有负环的情况,从1跑一次求最短路dis[n]
    return 0;
}
/*
10 2 1
2 3 2
3 4 2
2 4 1012
ans:-1
*/