差分约束

（1）求不等式组的可行解

源点需满足的条件：从源点出发，一定可以到达所有的边

求最短路

步骤：1.先将每个不等式xi<=xj + ck，转化成一条从xj走到xi，长度为ck的一条边

2.找一个超级源点，使得该源点一定可以遍历到所有的边

3.从该源点求一遍单源最短路

结果1：如果存在负环，则原不等式一定无解

结果2：如果没有负环，则dist[i]就是原不等式组的一个可行解

（2）如何求最大值或者最小值（这里的最值指的是每个变量的最值）

问题：如何转化xi<=c，其中c是一个常数，这类的不等式

方法：建立一个超级源点0，然后建立一条0->i，长度为c的边

结论：如果求的是最小值，则应该求最长路；如果求的是最大值，则应该求最短路

1169. 糖果 - AcWing题库

超时：用队列来写

import java.util.*;

//要求最小值应求最长路
public class Main{
    static int N = 100010, M = 3 * N;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static long[] dist = new long[N];
    static boolean[] st = new boolean[N];
    static int[] q = new int[N];
    static int[] cnt = new int[N];//边数
    static int n, m, idx;
    
    //邻接表存储
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    
    public static boolean spfa(){
        Arrays.fill(dist, -0x3f3f3f3f);//求最长路，应更新为负无穷
        int hh = 0, tt = 1;
        q[0] = 0;
        dist[0] = 0;
        st[0] = true;
        
        while(hh != tt){
            int t = q[hh ++];//一开始写成循环队列
            if(hh == N) hh = 0;
            st[t] = false;
            
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] < dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if(cnt[j] >= n + 1) return true;
                    if(!st[j]){
                        q[tt ++] = j;
                        if(tt == N) tt = 0;
                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        Arrays.fill(h, -1);//初始化队头
        
        while(m -- > 0){
            int x = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if(x == 1){
                add(b, a, 0);
                add(a, b, 0);
            }else if(x == 2){
                add(a, b, 1);
            }else if(x == 3){
                add(b, a, 0);
            }else if(x == 4){
                add(b, a, 1);
            }else add(a, b, 0);
        }
        
        for(int i = 1; i <= n; i ++){
            add(0, i, 1);//超级源点到每个点连一条边
        }
        
        if(spfa()){
            System.out.print("-1");
        }else{
            long res = 0;
            for(int i = 1; i <= n; i ++){
                res += dist[i];
            }
            System.out.print(res);
        }
    }
}

正确解法：用栈来写

import java.util.*;

//要求最小值应求最长路
public class Main{
    static int N = 100010, M = 3 * N;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static long[] dist = new long[N];
    static boolean[] st = new boolean[N];
    static int[] q = new int[N];
    static int[] cnt = new int[N];//边数
    static int n, m, idx;
    
    //邻接表存储
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    
    public static boolean spfa(){
        Arrays.fill(dist, -0x3f3f3f3f);//求最长路，应更新为负无穷
        Stack<Integer> sk = new Stack<>();//栈
        sk.push(0);
        dist[0] = 0;
        st[0] = true;
        
        while(!sk.isEmpty()){
            int t = sk.pop();//一开始写成循环队列

            st[t] = false;
            
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] < dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if(cnt[j] >= n + 1) return true;
                    if(!st[j]){
                        sk.push(j);
                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        Arrays.fill(h, -1);//初始化队头
        
        while(m -- > 0){
            int x = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if(x == 1){
                add(b, a, 0);
                add(a, b, 0);
            }else if(x == 2){
                add(a, b, 1);
            }else if(x == 3){
                add(b, a, 0);
            }else if(x == 4){
                add(b, a, 1);
            }else add(a, b, 0);
        }
        
        for(int i = 1; i <= n; i ++){
            add(0, i, 1);//超级源点到每个点连一条边
        }
        
        if(spfa()){
            System.out.print("-1");
        }else{
            long res = 0;
            for(int i = 1; i <= n; i ++){
                res += dist[i];
            }
            System.out.print(res);
        }
    }
}

正确解法：手写栈

import java.util.*;

//要求最小值应求最长路
public class Main{
    static int N = 100010, M = 3 * N;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static long[] dist = new long[N];
    static boolean[] st = new boolean[N];
    static int[] q = new int[N];
    static int[] cnt = new int[N];//边数
    static int n, m, idx;
    
    //邻接表存储
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    
    public static boolean spfa(){
        Arrays.fill(dist, -0x3f3f3f3f);//求最长路，应更新为负无穷
        int hh = 0, tt = 1;
        q[0] = 0;
        dist[0] = 0;
        st[0] = true;
        
        while(hh != tt){
            int t = q[-- tt];//手写栈
            st[t] = false;
            
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] < dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if(cnt[j] >= n + 1) return true;
                    if(!st[j]){
                        q[tt ++] = j;

                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        Arrays.fill(h, -1);//初始化队头
        
        while(m -- > 0){
            int x = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if(x == 1){
                add(b, a, 0);
                add(a, b, 0);
            }else if(x == 2){
                add(a, b, 1);
            }else if(x == 3){
                add(b, a, 0);
            }else if(x == 4){
                add(b, a, 1);
            }else add(a, b, 0);
        }
        
        for(int i = 1; i <= n; i ++){
            add(0, i, 1);//超级源点到每个点连一条边
        }
        
        if(spfa()){
            System.out.print("-1");
        }else{
            long res = 0;
            for(int i = 1; i <= n; i ++){
                res += dist[i];
            }
            System.out.print(res);
        }
    }
}

362. 区间 - AcWing题库

import java.util.*;

public class Main{
    static int N = 50010, M = 3 * N + 10;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, idx;
    
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    
    public static void spfa(){
        Arrays.fill(dist, -0x3f3f3f3f);//求最小值也就是求最长路，先初始化为负无穷
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        dist[0] = 0;
        st[0] = true;
        
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] < dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        Arrays.fill(h, -1);
        
        for(int i = 1; i < N; i ++){
            add(i - 1, i, 0);
            add(i, i - 1, -1);
        }
        
        while(n -- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            a ++;//整体右移一位
            b ++;
            add(a - 1, b, c);
        }
        
        spfa();//数据保证一定有解，不用判断是否有负环
        
        System.out.print(dist[50001]);
    }
}

1170. 排队布局 - AcWing题库

import java.util.*;

public class Main{
    static int N = 1010, M = 21010, INF = 0x3f3f3f3f;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int[] dist = new int[N];
    static int[] cnt = new int[N];
    static boolean[] st = new boolean[N];
    static int n, ml, md, idx;
    
    public static void temp(int a, int b){
        int temp = a;
        a = b;
        b = a;
    }
    
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    
    public static boolean spfa(int size){
        Arrays.fill(dist, INF);
        Arrays.fill(cnt, 0);
        Arrays.fill(st, false);
        
        Queue<Integer> q = new LinkedList<>();
        for(int i = 1; i <= size; i ++){
            dist[i] = 0;
            q.offer(i);
            st[i] = true;
        }
        
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if(cnt[j] >= n) return true;
                    
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h, -1);
        
        n = sc.nextInt();
        ml = sc.nextInt();
        md = sc.nextInt();
        
        for(int i = 1; i < n; i ++){
            add(i + 1, i, 0);
        }
        
        while(ml -- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if(b < a) temp(a, b);
            add(a, b, c);
        }
        
        while(md -- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            if(b < a) temp(b, a);
            add(b, a, -c);
        }
        
        if(spfa(n)) System.out.print("-1");//判断是否有负环
        else{
            spfa(1);
            if(dist[n] == INF) System.out.print("-2");
            else System.out.print(dist[n]);
        }
    }
}

393. 雇佣收银员 - AcWing题库

import java.util.*;

public class Main{
    static int N = 30, M = 110;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int[] dist = new int[N];
    static int[] cnt = new int[N];
    static int[] r = new int[N];//最小需求量
    static int[] nums = new int[N];//申请数
    static boolean[] st = new boolean[N];
    static int n, idx;
    
    //邻接表存储
    public static void add(int a, int b, int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    
    //建图
    public static void build(int c){
        Arrays.fill(h, -1);//多组数据，每次都要进行初始化
        idx = 0;
        
        add(0, 24, c);
        add(24, 0, -c);
        
        for(int i = 1; i <= 24; i ++){
            add(i - 1, i, 0);
            add(i, i - 1, - nums[i]);
        }
        
        for(int i = 1; i <= 7; i ++){
            add(i + 16, i, r[i] - c);
        }
        
        for(int i = 8; i <= 24; i ++){
            add(i - 8, i, r[i]);
        }
    }
    
    public static boolean spfa(int c){
        build(c);
        
        Arrays.fill(dist, -0x3f3f3f3f);
        Arrays.fill(st, false);
        Arrays.fill(cnt, 0);
        
        Queue<Integer> q = new LinkedList<>();
        dist[0] = 0;
        st[0] = true;
        q.offer(0);
        
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;
            
            for(int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] < dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1;
                    if(cnt[j] >= 25) return false;
                    
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return true;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T -- > 0){
            for(int i = 1; i <= 24; i ++){
                r[i] = sc.nextInt();
            }
            
            Arrays.fill(nums, 0);
            n = sc.nextInt();
            for(int i = 0; i < n; i ++){
                int t = sc.nextInt();
                nums[t + 1] ++;
            }
            
            boolean flag = false;
            for(int i = 0; i <= 1000; i ++){//枚举所有s24可能的值
                if(spfa(i)){
                    System.out.println(i);
                    flag = true;//只要有一个可以就行
                    break;
                }
            }
            
            if(!flag) System.out.println("No Solution");
        }
    }
}