算法笔记6

2024/4/8 算法 DFS BFS 图论最短路拓补排序最小生成树二分图

第三章搜索与图论

1. DFS

这里对角线数组，利用了斜率为1的直线截距，y = x + b 和 y = -x + b

那么 b = y - x 或 b = y + x

对应截距位置是否为true，表示该直线上是否有皇后

反对角线：

正对角线：

由于y - x可能为负，因此加一个偏置n，即n + y - x

这样两个对角线数组，只需要开2n大小就能满足

> acwing 843. n-皇后问题 https://www.acwing.com/problem/content/description/845/

import java.util.*;

class Main {
    static char[][] g;
    static boolean[] col;
    static boolean[] dg;    //对角线
    static boolean[] udg;   //反对角线
    static int n;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        g = new char[n][n];
        col = new boolean[n];
        dg = new boolean[2 * n];
        udg = new boolean[2 * n];
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], '.');
        }
        dfs(0);
        
        sc.close();
    }
    public static void dfs(int x) {
        if (x == n) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(g[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dg[x + i] && !udg[n + x - i]) {
                g[x][i] = 'Q';
                col[i] = dg[x + i] = udg[n + x - i] = true;
                dfs(x + 1);
                col[i] = dg[x + i] = udg[n + x - i] = false;
                g[x][i] = '.';
            }
        }
    }
}

2. BFS

acwing 844. 走迷宫 https://www.acwing.com/problem/content/846/

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] g = new int[n][m];
        int[][] dis = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = sc.nextInt();
                dis[i][j] = -1;
            }
        }
        dis[0][0] = 0;
        
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0});
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] pair = q.pollFirst();
                int x = pair[0], y = pair[1];
                
                if (x == n - 1 && y == m - 1) {
                    System.out.println(dis[x][y]);
                    return;
                }
                for (int j = 0; j < 4; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && g[nx][ny] == 0 && dis[nx][ny] == -1) {
                        q.add(new int[]{nx, ny});
                        dis[nx][ny] = dis[x][y] + 1;
                    }
                }
                
            }
        }
        
        sc.close();
    }
}

acwing 845. 八数码 https://www.acwing.com/problem/content/847/

bfs暴力枚举，记录第一次交换成某种字符串的次数（bfs保证了交换次数最少）

将3 * 3 网格用一个字符串表示，当枚举到"12345678x"，就解决了问题

枚举完所有可能都不行，就返回-1

import java.util.*;

class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < 9; i++) {
            sb.append(sc.next());
        }
        
        String start = sb.toString(), target = "12345678x";
        Deque<String> q = new ArrayDeque<>();
        Map<String, Integer> dist = new HashMap<>();
        dist.put(start, 0);
        q.add(start);
        
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String t = q.pollFirst();
                
                if (t.equals(target)) {
                    System.out.println(dist.get(t));
                    return;
                }
                //换成2维坐标
                int idx = t.indexOf('x');
                int x = idx / 3, y = idx % 3;
                
                for (int j = 0; j < 4; j++) {
                    int a = x + dx[j];
                    int b = y + dy[j];
                    int pos = a * 3 + b;
                    //不能pos >= 0 && pos < 9，因为可能a = 0，b = 3
                    if (a >= 0 && b >= 0 && a < 3 && b < 3) {
                        char[] cs = t.toCharArray();
                        //x和上下左右交换
                        swap(cs, pos, idx);
                        
                        String newStr = new String(cs);
                        if (!dist.containsKey(newStr)) {
                            //第一次变成该newStr，交换次数最少，记录下来，以后不再交换成该字符串
                            dist.put(newStr, dist.get(t) + 1);
                            q.add(newStr);
                        }
                    }
                }
                
            }
        }
        System.out.println(-1);
        sc.close();
    }
    public static void swap(char[] cs, int a, int b) {
        char tmp = cs[a];
        cs[a] = cs[b];
        cs[b] = tmp;
    }
}

3. 树与图的深度优先遍历

acwing 846. 树的重心 https://www.acwing.com/problem/content/description/848/

题目求的是，当删除某个节点后，使得其余连通块大小的最大值最小

对于每个节点来说，删除该节点后，可以分为以下几个部分

以每个子节点为根的树（总共有，与删除节点相连的节点个数，这么多个）
去掉自己这个节点为根的树，整棵树剩下的部分（1个部分，总节点数减去以删除节点为根的树的节点个数）

总节点数已知，因此我们需要知道某棵树的节点个数

通过dfs的返回值，可以返回节点总数

import java.util.*;

class Main {
    static List<Integer>[] g;
    static boolean[] vis;
    static int res;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        g = new List[n + 1];
        vis = new boolean[n + 1];
        
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            //无向图，双向
            add(a, b);
            add(b, a);
        }
        res = 100010;
        //也可以只搜一个结点，因为树是无环的连通的图
        //这里搜一个就会访问所有的，也就等价于dfs(1)
        for (int i = 1; i <= n; i++) {
            dfs(i);
        }
        System.out.println(res);
        
        sc.close();
    }
    
    public static int dfs(int x) {
        //节点数
        int sum = 1;
        //删除当前节点后，其余连通块大小的最大值
        int now = 0;
        for (Integer i : g[x]) {
            if (!vis[i]) {
                vis[i] = true;
                int t = dfs(i);
                now = Math.max(t, now);
                sum += t;
            }
        }
        //跟去掉自己这个节点为根的树，整棵树剩下的部分比较
        now = Math.max(n - sum, now);
        //记录最大值的最小值
        res = Math.min(res, now);
        return sum;
    }
    
    public static void add(int a, int b) {
        g[a].add(b);
    }
}

4. 树与图的广度优先遍历

acwing 847. 图中点的层次 https://www.acwing.com/problem/content/849/

因为边的长度都为1，所以可以BFS

import java.util.*;

class Main {
    static List<Integer>[] g;
    static int[] dis;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        int m = sc.nextInt();
        g = new List[n + 1];
        dis = new int[n + 1];
        Arrays.fill(dis, -1);
        
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            add(a, b);
        }
        
        Deque<Integer> q = new ArrayDeque<>();
        q.add(1);
        dis[1] = 0;
        while (!q.isEmpty()) {
            int x = q.pollFirst();
            for (int i = 0; i < g[x].size(); i++) {
                int t = g[x].get(i);
                if (dis[t] == -1) {
                    dis[t] = dis[x] + 1;
                    q.add(t);
                }
            }
        }
        
        System.out.println(dis[n]);
        
        sc.close();
    }
    
    public static void add(int a, int b) {
        g[a].add(b);
    }
}

5. 拓扑排序

acwing 848. 有向图的拓扑序列 https://www.acwing.com/problem/content/description/850/

注意：该拓步序列必须包含所有点

主要是用一个数组记录每个节点的入度

入度为0，就遍历，遍历完当前节点，对于指向的其他节点，入度要减减

import java.util.*;

class Main {
    static List<Integer>[] g;
    static int[] d; //入度
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        int m = sc.nextInt();
        g = new List[n + 1];
        d = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            /* 有自环的时候，无法构成拓步序列（因此不能注释中的这样），直接无脑add就行
            if (a != b) {
                add(a, b);
                d[b]++;
            }   */
            add(a, b);
            d[b]++;
        }
        
        Deque<Integer> q = new ArrayDeque<>();
        
        for (int i = 1; i <= n; i++) {
            if (d[i] == 0) {
                q.add(i);
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!q.isEmpty()) {
            int x = q.pollFirst();
            res.add(x);
            
            for (int t : g[x]) {
                d[t]--;
                if (d[t] == 0) {
                    q.add(t);
                }
            }
            
        }
        int len = res.size();
        if (len < n) {
            System.out.print(-1);
            return;
        }
        for (int i = 0; i < len; i++){
            System.out.print(res.get(i) + " ");
        }
        
        sc.close();
    }
    
    public static void add(int a, int b) {
        g[a].add(b);
    }
}

6. 最短路

$最短路单源最短路所有边权都是正数朴素算法堆优化版的算法存在负边权可以求最多不超过条边的最短路（可负环）一般，最坏多源最短路算法可处理负边$

6.1 Dijkstra

acwing 849. Dijkstra求最短路 I https://www.acwing.com/problem/content/851/

import java.util.*;

class Main {
    static int[][] g;
    static boolean[] check;
    static int[] dist;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        g = new int[n + 1][n + 1];
        //初始化为距离为+∞
        for (int i = 1; i <= n; i++) {
            Arrays.fill(g[i], Integer.MAX_VALUE);
        }
        dist = new int[n + 1];
        //是否确定距离
        check = new boolean[n + 1];
        //初始化点1到点n的距离为+∞
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            //重边选择最短边
            g[x][y] = Math.min(g[x][y], z);
        }
        //每次确定起点到某个点的最短距离，最多n次，就全部确定，得到结果
        for (int i = 1; i <= n; i++) {
            //在没确定的点中，找出最短的点
            int x = -1;
            for (int j = 1; j <= n; j++) {
                if (!check[j]) {
                    if (x == -1) {
                        x = j;
                    } else {
                        x = dist[j] < dist[x] ? j : x;
                    }
                }
            }
            check[x] = true;
            //如果剩下最短的全是+∞，直接结束循环（或者用0x3f3f3f3f表示+∞，不然的话会溢出，导致错误）
            if (dist[x] == Integer.MAX_VALUE) {
                break;
            }
            
            for (int j = 1; j <= n; j++) {
                //存在该条有向边，且距离更大
                if (g[x][j] != Integer.MAX_VALUE && dist[j] > dist[x] + g[x][j]) {
                    dist[j] = dist[x] + g[x][j];
                }
            }
        }
        System.out.println(dist[n] == Integer.MAX_VALUE ? -1 : dist[n]);
        
        sc.close();
    }
}

acwing 850. Dijkstra求最短路 II https://www.acwing.com/problem/content/852/

注意：堆必须存下当前的距离dist，不能只存下标，因为下标对应的距离在变化

import java.util.*;

class Main {
    static List<int[]>[] g;
    static boolean[] check;
    static int[] dist;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        g = new List[n + 1];
        
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        dist = new int[n + 1];
        //是否确定距离
        check = new boolean[n + 1];
        //初始化点1到点n的距离为+∞
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            //重边不影响
            g[x].add(new int[]{y, z});
        }
        //直接存下标，结果错误，可能是因为距离是直接在dist数组更新了，原本的最小堆在变动时，会破坏堆结构，导致错误
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        
        pq.add(new int[]{0, 1});
        
        //每次确定起点到某个点的最短距离，最多n次，就全部确定，得到结果
        for (int i = 1; i <= n; i++) {
            
            //在没确定的点中，找出最短的点。去除冗余信息（已确定的点的之前的值）
            int x = -1;
            while (!pq.isEmpty()) {
                x = pq.poll()[1];
                if (!check[x]) {
                    break;
                }
            }
            //找不到了
            if (x == -1) {
                break;
            }
            
            check[x] = true;
            
            for (int[] e : g[x]) {
                int j = e[0], w = e[1];

                if (dist[j] > dist[x] + w) {
                    dist[j] = dist[x] + w;
                    //加入更新后的距离，保证堆顶的值一定会是正确的（最短的），使之前的旧值在下面
                    pq.add(new int[]{dist[j], j});
                }
            }
        }
        System.out.println(dist[n] == Integer.MAX_VALUE ? -1 : dist[n]);
        
        sc.close();
    }
}

6.2 bellman-ford

k次循环，保证最多不超过k条边的最短路（如果存在负环，也可以求不超过k条边，即控制负环最多能走多少）

算法：

for k次循环：

遍历所有边（x, y, z）：

dist[y] = Math.min(dist[y], backup[x] + z); //松弛操作

使用Integer.MAX_VALUE：

import java.util.*;

class Main {
    static List<int[]> edges;
    //backup保证了每次更新不超过1条边，不用的话，可能前一条边更新后，把当前边再更新，相当于经过两条边，比如输入样例的数据
    static int[] dist, backup;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        edges = new ArrayList<>();
        dist = new int[n + 1];
        backup = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(backup, Integer.MAX_VALUE);
        dist[1] = 0;
        backup[1] = 0;
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            edges.add(new int[]{x, y, z});
        }
        
        for (int i = 0; i < k; i++) {
            for (int[] edge : edges) {
                int x = edge[0], y = edge[1], z = edge[2];
                if (backup[x] != Integer.MAX_VALUE) {
                    dist[y] = Math.min(dist[y], backup[x] + z);
                }
            }
            backup = Arrays.copyOf(dist, dist.length);
        }
        System.out.println(dist[n] == Integer.MAX_VALUE ? "impossible" : dist[n]);
        sc.close();
    }
}

使用0x3f3f3f3f（与上面不同的地方用//标注出来了）:

import java.util.*;

class Main {
    static List<int[]> edges;
    static int[] dist, backup;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        edges = new ArrayList<>();
        dist = new int[n + 1];
        backup = new int[n + 1];
        //
        Arrays.fill(dist, 0x3f3f3f3f);
        Arrays.fill(backup, 0x3f3f3f3f);
        //
        dist[1] = 0;
        backup[1] = 0;
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            edges.add(new int[]{x, y, z});
        }
        
        for (int i = 0; i < k; i++) {
            for (int[] edge : edges) {
                int x = edge[0], y = edge[1], z = edge[2];
                //
                dist[y] = Math.min(dist[y], backup[x] + z);
                //
            }
            backup = Arrays.copyOf(dist, dist.length);
        }
        //可能存在负权边，导致更新成 < 0x3f3f3f3f / 2
        System.out.println(dist[n] >= 0x3f3f3f3f / 2 ? "impossible" : dist[n]);
        //
        sc.close();
    }
}

6.3 spfa

是bellman-ford算法的优化

优化思路：

原本的bellman-ford算法中核心的是dist[y] = Math.min(dist[y], backup[x] + z);

而这个dist[y]更新只依赖于backup[x]，也就是前一次变小了的点（如果前一次不变的话，这次也不会变）

所以只需要存下变小了的点（已经存了的，就再不存了），对出边进行判断

一般时间复杂度为O（m），最坏情况O（nm）

（一般来说，需要堆优化的dijkstra问题O（mlogn），也可以用spfa，但也可能被卡最坏情况O（nm））

spfa也可以求有边数限制的最短路 https://www.acwing.com/solution/content/46468/

但是感觉bellman-ford更简单，推荐直接用bellman-ford

acwing 851. spfa求最短路 https://www.acwing.com/problem/content/853/

import java.util.*;

class Main {
    static List<int[]>[] g;
    static boolean[] check;
    //不需要backup数组，因为不用考虑不超过k条边的情况
    static int[] dist;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        g = new List[n + 1];
        
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        dist = new int[n + 1];
        check = new boolean[n + 1];
        //初始化点1到点n的距离为+∞
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            g[x].add(new int[]{y, z});
        }
        Deque<Integer> q = new ArrayDeque<>();
        q.add(1);
        check[1] = true;
        
        while (!q.isEmpty()) {
            int t = q.poll();
            check[t] = false;
            
            for (int[] e : g[t]) {
                int x = e[0], c = e[1];
                if (dist[x] > dist[t] + c) {
                    dist[x] = dist[t] + c;
                    if (!check[x]) {
                        q.add(x);
                        check[x] = true;
                    }
                }
            }
            
        }
        
        System.out.println(dist[n] == Integer.MAX_VALUE ? "impossible" : dist[n]);
        
        sc.close();
    }
}

acwing 852. spfa判断负环 https://www.acwing.com/problem/content/854/

注意是负环

import java.util.*;

class Main {
    static List<int[]>[] g;
    static boolean[] check;
    static int[] dist, cnt;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        g = new List[n + 1];
        
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        //无需初始化，全0、全无穷都无影响，因为只需要通过负边变小即可（重点是变小的趋势）
        dist = new int[n + 1];
        check = new boolean[n + 1];
        cnt = new int[n + 1];
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            g[x].add(new int[]{y, z});
        }
        
        Deque<Integer> q = new ArrayDeque<>();
        //全加进来，因为负环不一定经过1号点
        for (int i = 1; i <= n; i++) {
            q.add(i);
            check[i] = true;
        }
        
        
        while (!q.isEmpty()) {
            int t = q.poll();
            check[t] = false;
            
            for (int[] e : g[t]) {
                int x = e[0], c = e[1];
                //最开始c为负才会更新
                if (dist[x] > dist[t] + c) {
                    dist[x] = dist[t] + c;
                    cnt[x] = cnt[t] + 1;
                    if (cnt[x] >= n) {
                        System.out.println("Yes");
                        return;
                    }
                    if (!check[x]) {
                        q.add(x);
                        check[x] = true;
                    }
                }
            }
            
        }
        
        System.out.println("No");
        
        sc.close();
    }
}

6.4 Floyd

详细讲解可参考：https://www.luogu.com.cn/problem/solution/B3647

设为u到 v 的路径上的所有顶点（不包括 u,v 自身）编号不大于 k，考察此时的最短路

初始状态： = g[u][v]

未改进算法：

for k <= n :

for u <= n :

for v <= n :

k只与k-1有关，因此需要一个backup暂存（防止右边k-1更新后变成k了）

对于：和

中间路径（不包括两端点）不经过k号点时，显然成立
选择中间路径（不包括两端点）经过k号点时，说明相比不经过k最短路更短，也即u->k->k存在负环，与无负环要求不符，因此不会经过k号点

故上面两式成立

所以有

k与k-1皆可，因此可以去掉第一维k

变成

改进后：

for k <= n :

for u <= n :

for v <= n :

acwing 854. Floyd求最短路 https://www.acwing.com/problem/content/856/

import java.util.*;

class Main {
    static int[][] g;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), q = sc.nextInt();
        g = new int[n + 1][n + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(i != j) {
                    g[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            g[x][y] = Math.min(g[x][y], z);
        }
        
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (g[i][k] != Integer.MAX_VALUE && g[k][j] != Integer.MAX_VALUE) {
                        g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                    }
                }
            }
        }
        
        for (int i = 0; i < q; i++) {
            int x = sc.nextInt(), y = sc.nextInt();
            System.out.println(g[x][y] == Integer.MAX_VALUE ? "impossible" : g[x][y]);
        }
        
        sc.close();
    }
}

7. 最小生成树

$最小生成树朴素版稠密图堆优化版一般不用稀疏图$

7.1 Prim

类似于Dijkstra

Prim也是for循环n次，每次确定一个点

但是Prim选的是在距已确定集合最短的点（Dijkstra是距离起点最短，但都是用dist数组就可以实现记录）

acwing 858. Prim算法求最小生成树 https://www.acwing.com/problem/content/860/

import java.util.*;

class Main {
    static int[][] g;
    // 与 已确定集合 的最短距离
    static int[] dist;
    // 是否在已确定集合
    static boolean[] check;
    static int n, m;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        g = new int[n + 1][n + 1];
        dist = new int[n + 1];
        check = new boolean[n + 1];
        //初始化
        for (int i = 1; i <= n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), w = sc.nextInt();
            //处理重边
            g[a][b] = g[b][a] = Math.min(g[a][b], w);
        }
        
        int res = Prim();
        if (res == Integer.MAX_VALUE) {
            System.out.println("impossible");
        } else {
            System.out.println(res);
        }
        
        sc.close();
    }
    //不可能的话，就返回+∞
    public static int Prim() {
        //初始加入1号点
        check[1] = true;
        for (int i = 2; i <= n; i++) {
            dist[i] = g[1][i];
        }
        
        int res = 0;
        for (int i = 2; i <= n; i++) {
            //在没有确定的点中，选取距 已确定集合 的最短的点
            int choice = -1;
            for (int j = 2; j <= n; j++) {
                if (!check[j] && (choice == -1 || dist[choice] > dist[j])) {
                    choice = j;
                }
            }
            if (dist[choice] == Integer.MAX_VALUE) {
                //选不出
                return Integer.MAX_VALUE;
            }
            res += dist[choice];
            check[choice] = true;
            
            for (int j = 1; j <= n; j++) {
                //也可以不判断，判断了res += dist[choice]就能放后面（因为负自环）
                if (j != choice) {
                    dist[j] = Math.min(dist[j], g[j][choice]);
                }
            }
            
            
        }
        return res;
    }
    
}

7.2 Kruskal

算法：

①边集排序

②for e : edges（边e：点a, b, 权w）

if a, b不连通（处理重边、自环，且保证生成树不含环）

就把边e加入到最小生成树中（即合并a，b所在集合）

显然，利用并查集可以实现判断是否连通、合并两集合

acwing 859. Kruskal算法求最小生成树 https://www.acwing.com/problem/content/861/

import java.util.*;

class Main {
    
    static class Edge {
        int a;
        int b;
        int w;
        Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    
    static int n, m;
    //边集
    static Edge[] edges;
    //并查集
    static int[] p;
    
    public static int find(int x) {
        if (x == p[x]) {
            return x;
        }
        p[x] = find(p[x]);
        return p[x];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        edges = new Edge[m];
        p = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), w = sc.nextInt();
            edges[i] = new Edge(a, b, w);
        }
        Arrays.sort(edges, (o1, o2) -> o1.w - o2.w);
        
        int cnt = 0, res = 0;
        for (Edge e : edges) {
            int a = e.a, b = e.b, w = e.w;
            int pa = find(a), pb = find(b);
            //保证生成树不含环
            //处理重边，因为排序，先选的是短边，长边就被排除了
            //处理自环，自环一定有pa == pb
            if (pa != pb) {
                p[pa] = pb;
                res += w;
                cnt++;
            }
        }
        if (cnt == n - 1) {
            System.out.println(res);
        } else {
            System.out.println("impossible");
        }
        sc.close();
    }
}

8. 二分图

$二分图染色法匈牙利算法实际运行一般远小于$

二分图当且仅当图中不含奇数环

8.1 染色法

注意：自环算奇数环，所以不是二分图

acwing 860. 染色法判定二分图 https://www.acwing.com/problem/content/862/

import java.util.*;

class Main {
    static List<Integer>[] g;
    static int[] color;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt(), m = sc.nextInt();
        g = new List[n + 1];
        color = new int[n + 1];
        //注意：不要用增强for循环，因为相当于只拿到一个指向g[i]的指针（即形参x = g[i]地址），x = new ArrayList<>()修改的是x
        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            g[a].add(b);
            g[b].add(a);
        }
        
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0 && !dfs(i, 1)) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
        
        sc.close();
    }
    
    public static boolean dfs(int x, int c) {
        color[x] = c;
        for (Integer i : g[x]) {
            //自环这里直接就处理成false了，所以不用管
            if (color[i] == color[x]) {
                return false;
            } else if (color[i] == 0) {
                //注意不要直接赋值，而是递归处理
                if (!dfs(i, 3 - c)) {
                    return false;
                }
            }
        }
        return true;
    }
}

8.2 匈牙利算法

对于左边的点，如果右边如果没配对，就直接匹配上，如果右边配对了，就看是否可以成功调整（也即是否有备胎，有的话，上面的点就选择备胎，这样就空出来了）

acwing 861. 二分图的最大匹配 https://www.acwing.com/problem/content/863/

import java.util.*;

class Main {
    static int n1;
    static int n2;
    static List<Integer>[] g;
    static int[] match;
    static boolean[] visit;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n1 = sc.nextInt();
        n2 = sc.nextInt();
        int m = sc.nextInt();
        g = new List[n1 + 1];
        match = new int[n2 + 1];
        visit = new boolean[n2 + 1];
        
        for (int i = 1; i <= n1; i++) {
            g[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            g[a].add(b);
        }
        
        int res = 0;
        for (int i = 1; i <= n1; i++) {
            //对于每个点，visit要重置，因为可能调整之前的安排
            Arrays.fill(visit, false);
            if (find(i)) {
                res++;
            }
        }
        System.out.println(res);
        
        sc.close();
    }
    
    public static boolean find(int x) {
        for (Integer i : g[x]) {
            //防止循环递归
            if (!visit[i]) {
                visit[i] = true;
                if (match[i] == 0 || find(match[i])) {
                    match[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
}

下面这种不用visit数组会导致MLE（应该是递归栈溢出）

分析原因：

虽然这里保证了match[i] != x，但还是可能无限的递归下去

比如下列数据：

3 2 5
1 1
1 2
2 1
2 2
3 2

当为3号find时，会递归到1号点进行find

而此时的1号点find会因为1 2这条边，又递归回1号点，导致无限递归下去

所以必须加一个visit数组，防止重复访问（对于同一个点，访问右边某个点过后，要么直接匹配or成功调整（直接返回了），要么不可能调整，后面也不需要再次访问了）

public static boolean find(int x) {
    for (Integer i : g[x]) {
        if (match[i] == 0) {
            match[i] = x;
            return true;
        } else if (match[i] != x) {
            if (find(match[i])) {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}

LOADING