差分约束

洛谷P1993小K的农场BFS-SPFA版

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=10010, maxm=10010;
struct edge{int t, w; edge *nxt; edge(int to, int val, edge *next){t=to, w=val, nxt=next;} };
edge *h[maxn];
void add(int u, int v, int w){ h[u]=new edge(v, w, h[u]); }
int n, m, flag, dis[maxn], instack[maxn];           //flag标记是否有负环
int inq[maxn], cnt[maxn]; 
bool SPFA(int x)
{
    queue<int> Q;
    Q.push(x);
    inq[x]=1, cnt[x]=1;
    while(!Q.empty())
    {
        int from=Q.front();
        Q.pop();
        inq[from]=0;
        for(edge *p=h[from]; p; p=p->nxt)
        {
            int to=p->t, w=p->w;
            if(dis[to]>dis[from]+w)
            {
                dis[to]=dis[from]+w;
                cnt[to]=cnt[from]+1;
                if(cnt[to]>n+1) return false;       //false有负环 
                if(!inq[to])
                {
                    Q.push(to);
                    inq[to]=1;
                }
            }
        }
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1, t, a, b, c; i<=m; i++)
    {
        scanf("%d", &t);
        if(t==1)    scanf("%d%d%d", &a, &b, &c), add(a, b, -c);
        if(t==2)    scanf("%d%d%d", &a, &b, &c), add(b, a, c);
        if(t==3)    scanf("%d%d", &a, &b), add(a, b, 0), add(b, a, 0);
    }
    for(int i=1; i<=n; i++) add(n+1, i, -1);        //加入一个指向所有点的超级结点，使图“联通”起来
                                                    //从n+1号点开始，只有负边才能启动松弛，所以，加入的边为-1
    flag=SPFA(n+1);
    if(flag)    printf("Yes\n");
    else        printf("No\n");
    return 0;
}

洛谷P1993小K的农场DFS-SPFA版，在差分约束类问题中，建议使用DFS的SPFA

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=10010, maxm=10010;
struct edge{int t, w; edge *nxt; edge(int to, int val, edge *next){t=to, w=val, nxt=next;} };
edge *h[maxn];
void add(int u, int v, int w){ h[u]=new edge(v, w, h[u]); }
int n, m, flag, dis[maxn], instack[maxn];           //flag标记是否有负环 
void SPFA(int x)
{
    instack[x]=1;
    for(edge *p=h[x]; p; p=p->nxt)
    {
        if(dis[p->t]>dis[x]+p->w)                   //因dis的初始值都是0，只有负边可以启动松弛，这样避免了大量无用的松弛操作
        {
            if(instack[p->t])
            {
                flag=true;
                return;
            }
            dis[p->t]=dis[x]+p->w;
            SPFA(p->t);
        }
    }
    instack[x]=0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1, t, a, b, c; i<=m; i++)
    {
        scanf("%d", &t);
        if(t==1)    scanf("%d%d%d", &a, &b, &c), add(a, b, -c);
        if(t==2)    scanf("%d%d%d", &a, &b, &c), add(b, a, c);
        if(t==3)    scanf("%d%d", &a, &b), add(a, b, 0), add(b, a, 0);
    }
    for(int i=1; i<=n; i++) add(n+1, i, -1);        //加入一个指向所有点的超级结点，使图“联通”起来
                                                    //从n+1号点开始，只有负边才能启动松弛，所以，加入的边为-1 
    flag=false;
    dis[n+1]=0;
    SPFA(n+1);
    if(flag)    printf("No\n");
    else        printf("Yes\n");
    return 0;
}

洛谷P3275糖果DFS-SPFA版，在差分约束类问题中，建议使用DFS的SPFA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100010;
int N, K, dis[maxn], flag, instack[maxn];
struct edge{ int t, w; edge *nxt; edge(int to, int val, edge *next){ t=to, w=val, nxt=next; }};
edge *h[maxn];
void add(int u, int v, int w){ h[u]=new edge(v, w, h[u]); }

void SPFA(int x)
{
    instack[x]=1;
    for(edge *p=h[x]; p; p=p->nxt)
    {
        if(flag)    return;
        if(dis[p->t]<dis[x]+p->w)                       //求最长路 
        {
            if(instack[p->t])
            {
                flag=true;
                return;
            }
            dis[p->t]=dis[x]+p->w;
            SPFA(p->t);
        }
    }
    instack[x]=0;
}

int main()
{
    scanf("%d%d", &N, &K);
    for(int i=1, x, a, b; i<=K; i++)
    {
        scanf("%d%d%d", &x, &a, &b);
        if(x==1)    add(b, a, 0), add(a, b, 0);
        if(x==2)    add(a, b, 1);
        if(x==3)    add(b, a, 0);
        if(x==4)    add(b, a, 1);
        if(x==5)    add(a, b, 0);
    }
    for(int i=N; i>=1; i--) add(N+1, i, 1);             //加边的顺序很重要，会极大影响搜索顺序
    SPFA(N+1);
    if(flag)    printf("-1\n");
    else
    {
        long long ans=0;                                //小心1~100000的数列和是超过int范围的 
        for(int i=1; i<=N; i++) ans+=dis[i];
        printf("%lld\n", ans);
    }
    return 0;
}

洛谷P3275糖果BFS-SPFA版，90分，TLE第6个点

//朴素BFS的SPFA会TLE一个点，SLL和SLF优化是否能过没有尝试，本题使用DFS的SPFA效率最高 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100010;
int N, K, dis[maxn], cnt[maxn], inq[maxn];
struct edge{ int t, w; edge *nxt; edge(int to, int val, edge *next){ t=to, w=val, nxt=next; }};
edge *h[maxn];
void add(int u, int v, int w){ h[u]=new edge(v, w, h[u]); }

bool SPFA(int x)
{
    queue<int> q;
    q.push(x);
    inq[x]=cnt[x]=1;
    while(!q.empty())
    {
        int from=q.front();
        q.pop();
        inq[from]=0;
        for(edge *p=h[from]; p; p=p->nxt)
        {
            int to=p->t, w=p->w;
            if(dis[to]<dis[from]+w)                     //求最长路
            {
                cnt[to]=cnt[from]+1;
                if(cnt[to]>N+1) return false;
                dis[to]=dis[from]+w;
                if(!inq[to])
                {
                    q.push(to);
                    inq[to]=1;
                }
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d%d", &N, &K);
    for(int i=1, x, a, b; i<=K; i++)
    {
        scanf("%d%d%d", &x, &a, &b);
        if(x==1)    add(b, a, 0), add(a, b, 0);
        if(x==2)    add(a, b, 1);
        if(x==3)    add(b, a, 0);
        if(x==4)    add(b, a, 1);
        if(x==5)    add(a, b, 0);
    }
    for(int i=N; i>=1; i--) add(N+1, i, 1);             //加边的顺序很重要，会极大影响搜索顺序 
    if(!SPFA(N+1))  printf("-1\n");
    else
    {
        long long ans=0;                                //小心1~100000的数列和是超过int范围的
        for(int i=1; i<=N; i++) ans+=dis[i];
        printf("%lld\n", ans);
    }
    return 0;
}

差分约束

原文：https://www.cnblogs.com/lfyzoi/p/10669511.html