完全背包问题：
实际上，完全背包问题就是在01背包问题的基础上，将每种物品的数量由1个变为无限个。
因此，完全背包问题中的递推式也将随之发生改变。在01背包问题中，其递推式为：
dp[i][j] = max( dp[i-1][j] , dp[i-1][j - w[i]] + v[i] )
基于以上公式在填表的第一行时，其结果如下：
可以看出，在填写第一行的第2、3、4列时，尽管背包容量增加了，但是由于耳机只有一个，所以后面背包的最大值一直未发生变化，其取值始终为一个耳机的价值。但是现在的情况有所不同，我们可以在不超过背包容量的前提下，多拿几个耳机。此时，填表的结果应该如下：
基于此，我们可以很自然地想到在01背包问题的算法中，于最内层再加一重循环，这层循环用于确定当前单元格（即dp[i][j]）到底取多少个物品会使得当前价值最大（但不能超过背包容量）。于是此时的状态转移方程就变成了（其中，k表示当前物品拿了多少个）：
dp[i][j] = max( dp[i-1][j] , dp[i-1][ j - k*w[i] ] + k*v[i] )
这便是完全背包问题中最关键的递推式了，下面我们同样以一个实际例题来练练手
public class demo74_疯狂的采药完全dp { static int M = 105; static int N = 1005; static int m, n; static int maxValue, temp;//组合寻找每一个格子的最大价值 static int[][] dp = new int[M][N]; static int[] t = new int[M]; static int[] v = new int[M]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); scanner.nextLine(); for (int i = 1; i <= m; i++) { t[i] = scanner.nextInt(); v[i] = scanner.nextInt(); scanner.nextLine(); } for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { maxValue = 0;//用于记录当前格中的最大值 for (int k = 0; k * t[i] <= j; k++) {//k表示当前物品拿了多少个。当k = 0时，表示不拿当前物品，即沿用上一层的数据 temp = k * v[i] + dp[i - 1][j - k * t[i]];//此时的价值 = k个当前物品的价值 + 剩余容量在上一层中对应的最大价值 if (temp > maxValue) maxValue = temp;//更新当前格中的最大价值 } dp[i][j] = maxValue;//记录该格中的最大价值 } System.out.println(dp[m][n]); } }
上述代码确实解决了完全背包问题，但是新问题也随之引出：
① 程序中使用了二维数组，在数据范围过大的情况下连编译都过不了；
② 程序中使用了三重循环，在数据范围稍大的情况下会超时。
接下来我们就着手对上面的问题进行优化。首先是降维，那就需要把状态转移方程变为：
dp[j] = max( dp[j] , dp[j - k*w[i]] + k*v[i] )
维度是降低了，但是更新方向呢？此时，我们突然想起某件事！！！在前面01背包问题中我们讨论降维时，出现了一个有趣的现象——如果更新dp数组时采用自左向右的方向，那么在后面进行更新时，其执行逻辑是“可重复拿取某件物品”！巧了，现在我们所作的假设就是所有物品都有无数件（即可重复拿），这不正好就可以拿来用了么？换言之，现在我们不再需要用最里面的那层k循环来确定某个网格到底拿多少物品才能使得背包总价值最大，而是通过采取和01背包问题中相反的更新dp数组方向来实现。
下面给出经过优化后的完整满分代码：
public class demo74_疯狂的采药_降维 { static int M = 100005; static int N = 10005; static int m, n; static int[] dp = new int[N]; static int[] t = new int[M]; static int[] v = new int[M]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); scanner.nextLine(); for (int i = 1; i <= m; i++) { t[i] = scanner.nextInt(); v[i] = scanner.nextInt(); scanner.nextLine(); } /** * 回顾01降维过程： * 第一个单元格，此时dp[1]=max(dp[1], dp[1-1]+1500)=max(0, 0+1500)=1500； * 第二个单元格，此时dp[2]=max(dp[2], dp[2-1]+1500)=max(dp[2], dp[1]+1500)=max(0, 1500+1500)=3000； * 第三个单元格，此时dp[3]=max(dp[3], dp[3-1]+1500)=max(dp[3], dp[2]+1500)=max(0, 3000+1500)=4500； * 第四个单元格，此时dp[4]=max(dp[4], dp[4-1]+1500)=max(dp[4], dp[3]+1500)=max(0, 4500+1500)=6000； */ for (int i = 1; i <= m; i++) for (int j = t[i]; j <= n; j++) { //如果正向拿取，正好达到重复拿取某一种物品的效果 dp[j] = Math.max(dp[j], v[i] + dp[j - t[i]]); } System.out.println(dp[n]); } }
多重背包问题：
一个正整数n，可以被分解成1,2,4,…,2(k-1),n-2k+1的形式。
在每一次的循环中，把拆分后的数不断重新组合并将每种组合的最大价值记录在滚动数组对应的位置，在最后一次循环的时，恰好列举出了拿该种物品1~number次每次的最大价值！值得深思与记忆！
问题描述
有容积为V的背包，给定一些物品，每种物品包含体积 w、价值 v、和数量 k，求用该背包能装下的最大价值总量。
算法分析
01背包问题与完全背包问题实际上是两种极端，而多重背包问题则正是介于这两者之间的一种情况。基于此，我们可以将多重背包问题转化为01背包或完全背包问题来进行求解。
① 可以把某种物品中的k个视为k种不同物品，此时再对所有物品按照01背包问题来进行处理。这样的转化当然是成立的，但是仅在数据范围较小时才适用，一旦每种物品的数量稍大一点，在时间上必然有超时的风险。此时，对于某种物品（假设有k个），若我们采用一种更精炼的划分方案，就会使得该物品分类下来的组数大大减少。比如可以采用二进制的拆分将原来的k个物品分为：{ 1、2、4、……、k - 2i + 1 } 这些组，以替代最初的分类：{ 1、1、1、……、1 } 这些组，这是一个log2(n)级别的数量优化。
② 若存在某个物品，其数量k乘以其单位体积大于背包总容量（即k*w[i] > V），那么此时对于该物品而言，它与背包之间是完全背包问题。
上述两点分别从01背包和完全背包的角度对多重背包问题进行了转化，而多重背包正好也是介于01背包和完全背包之间的问题。正是这两点，使得我们能设计出一个可以与“单调队列优化”分庭抗衡的算法。下面还是用一个实际例题来练手，以巩固理解。
public class demo75_超市里的狂欢夜_多重dp { static int N = 100005; static int M = 10005; static int n, m;//m行 n列 static int[] dp = new int[N]; static int[] w = new int[M]; static int[] v = new int[M]; static int[] num = new int[M]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt();//列 m = scanner.nextInt();//行 scanner.nextLine(); for (int i = 1; i < m; i++) { w[i] = scanner.nextInt(); v[i] = scanner.nextInt(); num[i] = scanner.nextInt(); scanner.nextLine(); } for (int i = 1; i <= m; i++) { MultiplePack(w[i], v[i], num[i]); } System.out.println(dp[n]); } static void ZeroOnePack(int weight, int value) { //01背包模型 for (int i = n; i >= weight; i--)//逆向 dp[i] = Math.max(dp[i], dp[i - weight] + value); } static void CompletePack(int weight, int value) { //完全背包模型 for (int i = weight; i <= n; i++)//正向 dp[i] = Math.max(dp[i], dp[i - weight] + value); } static void MultiplePack(int weight, int value, int number) { //多重背包模型 if (number * weight > n) {//如果总容量比这个物品的容量要小，那就退化为完全背包 CompletePack(weight, value); } else {//否则就将其转化为01背包（并利用二进制的拆分来优化）{ 1、2、4、……、k - 2i + 1 } 最后一个为一个常数c int k = 1; while (k <= number) { ZeroOnePack(k * weight, k * value); number -= k; k = k << 2; } //对余下的常数c进行处理 if (number != 0) ZeroOnePack(number * weight, number * value); } } }
分组背包问题：
问题描述： 有n件物品，分为若干组，现约束，在每组物品里最多取一件物品放入背包，每件物品的重量确定，价值确定，背包容量确定，求在不超过背包容量的情况下，可以存放的最大价值。 解决思路： 1. 状态表示：首先定义一个二维数组f[i][j],用它来表示：所有只从前i个物品中选，并且总体积不超过j的选法，且其属性为求最大值max。 2. 状态计算：先将集合f[i][j]分成若干等分，，每一份表示第i组物品选哪个； 最后求（1）和（2）的最大值即可得到转移方程。
模板题：
有 N组物品和一个容量是 V 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。 输入格式 第一行有两个整数N，V，用空格隔开，分别表示物品组数和背包容量。 接下来有 N 组数据： 每组数据第一行有一个整数 Si，表示第 ii 个物品组的物品数量； 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值； 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤100 0<Si≤100 0<vij,wij≤100 输入样例 3 5 2 1 2 2 4 1 3 4 1 4 5 输出样例： 8
public class demo76_分组背包 { static int n, m;//组数、容量 static int[][] v = new int[110][110];//第i组第j个物品的体积 static int[][] w = new int[110][110];//第i组第j个物品的价值 static int[] s = new int[110];//第i组的物品种数 static int[] dp = new int[110];//背包中体积为i时的最大价值 static Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { n = scanner.nextInt();//n组物品 m = scanner.nextInt();//背包容量 for (int i = 1; i <= n; i++) {//组别 s[i] = scanner.nextInt();//每组有多少种物品 for (int j = 0; j < s[i]; j++) {//存储每组每种物品的体积和价值 v[i][j] = scanner.nextInt();//体积 w[i][j] = scanner.nextInt();//价值 } } for (int i = 1; i <= n; i++) {//枚举组 for (int j = m; j >= 0; j--) {//枚举容量 for (int k = 0; k < s[i]; k++) {//枚举第i组中的每种物品 if (v[i][k] <= j) {//能装下 dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);//滚动数组降维，前者代表不拿的最大价值，后者代表拿的最大价值 } } } } System.out.println(dp[m]); } }
区间dp
关路灯
package java_Algorithm.self.train01; import java.util.Arrays; import java.util.Scanner; /** * @Author: LiangXinRui * @Date: 2023/03/02/10:40 * @Description: 某一村庄在一条路线上安装了 n 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。 * 老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 * 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关， * 但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。 * 开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯， * 而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。 * 现在已知老张走的速度为 1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W）， * 老张关灯所用的时间很短而可以忽略不计。 * <p> * 第一行是两个数字 n（表示路灯的总数）和 c（老张所处位置的路灯号）； * 接下来 n 行，每行两个数据，表示第 1 盏到第 n 盏路灯的位置和功率。数据保证路灯位置单调递增。 * <p> * 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。 * @Description: 思路： 本题与上一题的区别在于合并区间的消耗方式不同，为功率x时间，速度为1m/s， * 所以消耗又可表示为功率x移动距离，因为要记录上一次所在位置才能知道到走到现在位置的距离， * 所以增加一维空间dp[i][j][0]表示关完 i ~ j 时，老张站在 i 点，dp[i][j][1]表示关完 i ~ j 时， * 老张站在 j 点，他只有这两种站法，因为区间 [i , j] 要么是[i + 1, j]往左走一格得来的，此时站在 i 点， * 要么是[i , j-1]向右走一格得来的，此时站在 j 点。所以这里的区间合并可以转换为上一个区间向左或向右走一步。 * 因此状态转移方程： * dp[i][j][0] = min(dp[i+1][j][0] + count(i, i+1, i+1, j, n), dp[i+1][j][1] + count(i, j, i+1, j, n)); * dp[i][j][1] = min(dp[i][j-1][0] + count(i, j, i, j-1, n), dp[i][j-1][1] + count(j-1, j, i, j-1, n)); */ //https://blog.csdn.net/Easenyang/article/details/124760843?spm=1001.2014.3001.5501 public class demo76_区间dp_关路灯 { static int[][][] dp = new int[51][51][2]; static int[] po = new int[51]; static int[] sum = new int[51]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), c = sc.nextInt(); for (int i = 1; i <= n; i++) { po[i] = sc.nextInt(); sum[i] = sum[i - 1] + sc.nextInt();//计算前缀和 for (int j = 1; j <= n; j++) {//将dp数组都初始化为一个超大的值，因为我们求的是最小功耗 dp[i][j][0] = dp[i][j][1] = Integer.MAX_VALUE / 3; } } dp[c][c][0] = dp[c][c][1] = 0; //初始位置的功耗为0 for (int len = 2; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; //count方法用来计算合并消耗 dp[i][j][0] = Math.min(dp[i + 1][j][0] + count(i, i + 1, i + 1, j, n), dp[i + 1][j][1] + count(i, j, i + 1, j, n)); dp[i][j][1] = Math.min(dp[i][j - 1][0] + count(i, j, i, j - 1, n), dp[i][j - 1][1] + count(j - 1, j, i, j - 1, n)); } } System.out.println(Math.min(dp[1][n][0], dp[1][n][1])); } /** * @param x, y 移动前、后的路灯位置 * @param l, r l~r的路灯都是关着的 * @param n 总路灯数 * @return (po[y] - po[x])相当于时间，(sum[n]-sum[r]+sum[l-1])为其他未关的灯的总功率 * <p> * 每次关完 i 到 j 后我们还要计算其他未关的路灯耗能多少，加上已关完路灯消耗的总耗能就是本次的耗能， * 对于未关路灯的总耗能，我们可以用前缀和来计算，sum[i]表示第一个到第i个路灯的总功率。 * 这里我们可以用一个函数count()来计算总耗能。 * <p> * 其中 x 和 y 是从第 y 个路灯走到第 x 个路灯，po数组是各自距起点的距离，po[y]-po[x]就是走的距离， * 速度1m/s，所以它又可以代表消耗的时间，l 和 r 表示第 l 个到第 r 个路灯是关闭的，n 是路灯总数， * sum[n]-sum[r]代表已关区间右边未关的灯的总功率sum[l-1]就是左边未关的灯的总功率，再乘以时间就是未关的灯消耗的总功率 */ public static int count(int x, int y, int l, int r, int n) { return (po[y] - po[x]) * (sum[n] - sum[r] + sum[l - 1]); } }
分治
//汉诺塔————子问题于父问题没有关联 public class Hanoitower { public static void main(String[] args) { hanoiTower(10, 'A', 'B', 'C'); } /** * 分治————处理汉诺塔的移动 * -------------------------写递归不要去细想子问题的过程，因为里面的参数会随之改变，绕起来很麻烦，你只需要想清楚最底层的那一步该怎么走， * -------------------------即：只需要想清楚“最子“的那个问题的所有情况该怎么处理，则其他父问题就和该问题一样得到解决，最终完成所有步骤 * -------------------------如：汉诺塔的”最子“问题就是：把所有的盘看成两个盘，“最下面的盘”和 ”其余的盘“ ，处理好这个问题后，其余问题随之解决 * -------------------------注意：递归程序一定要写好递归出口，其余步骤交给递归程序来完成 * @param num 需要移动的塔盘数目 * @param a 起点 * @param b 中转 * @param c 终点 */ public static void hanoiTower(int num, char a, char b, char c) { //如果只有一个盘 if(num == 1) { System.out.println("第1个盘从 " + a + "->" + c); } else { //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘 //1. 先把 上面的所有盘（num - 1个）从A->B， 移动过程会使用到 c hanoiTower(num - 1, a, c, b); //2. 把最下边的盘 A->C System.out.println("第" + num + "个盘从 " + a + "->" + c); //3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔 hanoiTower(num - 1, b, a, c); } } }
贪心
//以覆盖问题为例 public class GreedyAlgorithm { public static void main(String[] args) { //创建广播电台,放入到Map HashMap<String, HashSet<String>> broadcasts = new HashMap<>(); //将各个电台放入到broadcasts HashSet<String> hashSet1 = new HashSet<>(); hashSet1.add("北京"); hashSet1.add("上海"); hashSet1.add("天津"); HashSet<String> hashSet2 = new HashSet<>(); hashSet2.add("广州"); hashSet2.add("北京"); hashSet2.add("深圳"); HashSet<String> hashSet3 = new HashSet<>(); hashSet3.add("成都"); hashSet3.add("上海"); hashSet3.add("杭州"); HashSet<String> hashSet4 = new HashSet<>(); hashSet4.add("上海"); hashSet4.add("天津"); HashSet<String> hashSet5 = new HashSet<>(); hashSet5.add("杭州"); hashSet5.add("大连"); //加入到map broadcasts.put("K1", hashSet1); broadcasts.put("K2", hashSet2); broadcasts.put("K3", hashSet3); broadcasts.put("K4", hashSet4); broadcasts.put("K5", hashSet5); //allAreas 存放所有的地区 HashSet<String> allAreas = new HashSet<>(); for (HashSet<String> value : broadcasts.values()) { allAreas.addAll(value); } //创建ArrayList, 存放选择的电台集合 List<String> selects = new ArrayList<>(); //定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集 HashSet<String> tempSet = new HashSet<>(); //定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key //如果maxKey 不为null , 则会加入到 selects String maxKey; while (allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区 //每进行一次while,需要 maxKey = null; //遍历 broadcasts, 取出对应key for (String key : broadcasts.keySet()) { //每进行一次for tempSet.clear(); //当前这个key能够覆盖的地区 HashSet<String> areas = broadcasts.get(key); tempSet.addAll(areas); //求出tempSet 和 allAreas 集合的交集, 交集会赋给 tempSet tempSet.retainAll(allAreas); //如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多 //就需要重置maxKey // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的 if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) { maxKey = key; } } //maxKey != null, 就应该将maxKey 加入selects if (maxKey != null) { selects.add(maxKey); //将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉 allAreas.removeAll(broadcasts.get(maxKey)); } } System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5] } }
Prim（普利姆）最小生成树
普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
普利姆的算法如下:
设G=(V,E)是连通网，T=(u,D)是最小生成树，v,u是顶点集合，E,D是边的集合。
若从顶点u开始构造最小生成树，则从集合v中取出顶点u放入集合u中，标记顶点v的visited[u]=1。
若集合u中顶点ui与集合v-u中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合u中，将边（ui,vj）加入集合D中，标记visited[vj]=1。
重复步骤②，直到u与v相等，即所有顶点都被标记为访问过，此时D中有n-1条边(5)提示:单独看步骤很难理解，我们通过代码来讲解，比较好理解。
自我理解：
创建一个空的存储顶点的点；
先确定一个点，将这个顶点和与它相邻的、还没访问过的顶点进行处理；
“处理”：比较满足条件的各个边，找出最小的边，将这个顶点加入刚才的顶点集合中；
- 再重复上面的操作，直到这个顶点集合中的顶点包含了图中的全部顶点。
//修路问题（最小生成树） public class PrimAlgorithmSimple { public static char[] data; public static int[][] matrix; public static boolean[] visited; public static final int N = Integer.MAX_VALUE; public static void main(String[] args) { data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'}; matrix = new int[][]{ {N, 5, 7, N, N, N, 2}, {5, N, N, 9, N, N, 3}, {7, N, N, N, 8, N, N}, {N, 9, N, N, N, 4, N}, {N, N, 8, N, N, 5, 4}, {N, N, N, 4, 5, N, 6}, {2, 3, N, N, 4, 6, N} }; visited = new boolean[data.length]; prim(1); } public static void prim(int startIndex) { visited[startIndex] = true; int isVisited = -1; int notVisited = -1; int minMatrix = Integer.MAX_VALUE; for (int k = 1; k < data.length; k++) {//一共需要length-1条边 for (int i = 0; i < data.length; i++)//查找已访问过的结点 for (int j = 0; j < data.length; j++)//查找未访问过的结点 if (visited[i] && !visited[j] && matrix[i][j] < minMatrix) {//找到权值最小的边，并记录这两个顶点 minMatrix = matrix[i][j]; isVisited = i; notVisited = j; } System.out.println("边<" + data[isVisited] + "," + data[notVisited] + "> 权值:" + minMatrix); visited[notVisited] = true;//标记访问过 minMatrix = Integer.MAX_VALUE;//重置 } } }
Kruskal（克鲁斯卡尔）最小生成树
克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想
按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法
首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
问题一：对图的所有边按照权值大小进行排序。
问题二：将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一很好解决，采用排序算法进行排序即可。
问题二的处理方式是:记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。
在将<E,F> <C,D><D,E>加入到最小生成树R中之后，这几条边的顶点就都有了终点:
- (01)C的终点是F。
- (02)D的终点是F。
- (03)E的终点是F。
- (04)F的终点是F。
- 关于终点的说明:（类似并查集）
1)就是将所有顶点按照从小到大的顺序排列好之后;某个顶点的终点就是"与它连通的最大顶点”"。
2)因此，接下来，虽然<C,E>是权值最小的边。但是C和E的终点都是F，即它们的终点相同，因此，将<C,E>加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，我们加入的边的两个顶点不能都指向同一个终点，否则将构成回路。
package java_Algorithm.self.train01; import java.io.*; import java.util.Arrays; /** * @Auther: LiangXinRui * @Date: 2023/3/31 9:30 * @Description: Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。 * 将排序好的权重边依次加入到最小生成树中（如果加入时产生回路就跳过这条边，加入下一条边）， * 当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树～ */ public class demo83_kruskal_修建公路 { static final int N = (int) (1e5 + 10), M = (int) (3e5 + 10); static int n, m; static Node[] edges = new Node[M]; static int[] pre = new int[N]; static int[] rank = new int[N]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static void init() { Arrays.fill(rank, 1); for (int i = 0; i <= n; i++) pre[i] = i; } static int find(int i) { if (pre[i] == i) return i; return find(pre[i]); } static void join(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] > rank[y]) pre[y] = x; else { if (rank[x] == rank[y]) rank[y]++; pre[x] = y; } } public static void main(String[] args) throws Exception { n = nextInt(); m = nextInt(); init(); for (int i = 0; i < m; i++) edges[i] = new Node(nextInt(), nextInt(), nextInt()); Arrays.sort(edges, 0, m); int cnt = 0; long sum = 0; for (int i = 0; i < m; i++) if (find(edges[i].start) != find(edges[i].end)) { join(edges[i].start, edges[i].end); sum += edges[i].weight; cnt++; } if (cnt == n - 1) out.println(sum); else out.println(-1); out.flush(); } static class Node implements Comparable<Node> { int start; int end; int weight; public Node(int start, int end, int weight) { this.start = start; this.end = end; this.weight = weight; } public int compareTo(Node e) { return weight - e.weight; } } static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } }
Dijkstra（迪杰斯特拉，得到某个点到各个点之间的最短距离）
朴素dijkstra（容易爆栈）
import java.util.Arrays; public class DijkstraAlgorithmSimpleMost { public static char[] vertex; public static int[][] matrix; public static final int N = Integer.MAX_VALUE >> 1; public static boolean[] visitedArr; public static int[] preArr; public static int[] disArr; public static void main(String[] args) { vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'}; matrix = new int[vertex.length][vertex.length]; matrix = new int[][]{ {N, 5, 7, N, N, N, 2}, {5, N, N, 9, N, N, 3}, {7, N, N, N, 8, N, N}, {N, 9, N, N, N, 4, N}, {N, N, 8, N, N, 5, 4}, {N, N, N, 4, 5, N, 6}, {2, 3, N, N, 4, 6, N}}; visitedArr = new boolean[vertex.length]; preArr = new int[vertex.length]; disArr = new int[vertex.length]; Arrays.fill(disArr, Integer.MAX_VALUE >> 1); dijkstra(2); show(); } //广度优先寻找最短路径。与bfs一样，设置一个起点并对其进行操作，遍历出其余符合条件的结点，并依次对其进行同样的操作 public static void dijkstra(int index) { visitedArr[index] = true; disArr[index] = 0; updatePreAndDis(index); for (int j = 1; j < vertex.length; j++) { index = updateIndex(); updatePreAndDis(index); } } //比较各个顶点通过index到自己与出发点到自己的距离，如果更小则设置index为自己的前驱，并更新出发点到自己的距离 private static void updatePreAndDis(int index) { int len; for (int j = 0; j < matrix[index].length; j++) { len = disArr[index] + matrix[index][j]; if (!visitedArr[j] && len < disArr[j]) { preArr[j] = index; disArr[j] = len; } } } //寻找当前未被访问过、并且距离出发点路程最短的结点，返回该结点的下标 public static int updateIndex() { int min = N, index = 0; for (int i = 0; i < visitedArr.length; i++) if (!visitedArr[i] && disArr[i] < min) { min = disArr[i]; index = i; } visitedArr[index] = true; return index; } public static void show() { char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int count = 0; for (int i : disArr) { if (i != Integer.MAX_VALUE >> 1) { System.out.print(vertex[count] + "(" + i + ") "); } else { System.out.println("N "); } count++; } System.out.println(); } }
堆优化的dijkstra（链式前向星）
点击上方蓝色字体，看我另外一篇文章，详细讲解链式前向星。
用堆优化来降低时间复杂度
时间复杂度降到nlogn+m
堆优化了每次找离起点最近的点的时间复杂度。
邻接表优化了对于每一个基点，更新它的所有邻边的时间复杂度（上面那个就是1扫到n，很花时间）
链式前向星+优先队列
import java.util.*; public class demo84_堆优化dijkstra_蓝桥王国 { static int[] head, next, ends; static long[] weights, dis;//权值和结果集 static int n, m, total;//n个顶点，m条边，++total：从第一条边到最后一条边 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); head = new int[m + 1];//表示以 i 为起点的最后一条边的编号 next = new int[m + 1];//存储与当前边起点相同的上一条边的编号 ends = new int[m + 1];//存储边的终点 weights = new long[m + 1];//存储边的权值 dis = new long[n + 1];//存储最终结果 Arrays.fill(head, -1);//初始化 for (int i = 0; i < m; i++) { int start = scanner.nextInt(); int end = scanner.nextInt(); long weight = scanner.nextLong(); add(start, end, weight); } dijkstra(1); for (int i = 1; i <= n; i++) if (dis[i] == Long.MAX_VALUE) System.out.print(-1 + " "); else System.out.print(dis[i] + " "); } private static void dijkstra(int startPoint) { for (int i = 1; i <= n; i++) { dis[i] = Long.MAX_VALUE;//初始化时，应当赋上最坏的情况 } Queue<Node> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.dis - o2.dis)); queue.offer(new Node(startPoint, weights[startPoint])); dis[startPoint] = 0;//起始位置，应当赋上最好的情况 while (!queue.isEmpty()) { Node x = queue.poll();//当前点 //链式前向星的遍历方法，遍历出以x为起点的所有边 for (int i = head[x.num]; i != -1; i = next[i]) {//i表示：第 i 条边 int j = ends[i];//第 i 条边的终点 if (dis[j] > dis[x.num] + weights[i]) {//如果length(起点-->终点) > length(起点 --> 当前点) + length(当前点 --> 终点) dis[j] = dis[x.num] + weights[i];//更新起点到终点的最短距离 queue.offer(new Node(j, dis[j]));//并将这个终点入队，以便之后通过该点访问其他顶点 } } } } static class Node { int num; long dis; public Node(int num, long dis) { this.num = num; this.dis = dis; } } private static void add(int start, int end, long weight) {//链式前向星的创建方法 ends[++total] = end; weights[total] = weight; next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号 head[start] = total;//更新以start为起点的上一条边的编号 } }
Floyd（弗洛伊德，得到各个点到各个点之间的最短距离）
import java.util.Arrays; public class FloydAlgorithmSimple { public static char[] vertex; public static int[][] pre; public static int[][] matrix; public static final int N = Integer.MAX_VALUE >> 1; public static void main(String[] args) { vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'}; pre = new int[vertex.length][vertex.length]; matrix = new int[][]{ {0, 5, 7, N, N, N, 2}, {5, 0, N, 9, N, N, 3}, {7, N, 0, N, 8, N, N}, {N, 9, N, 0, N, 4, N}, {N, N, 8, N, 0, 5, 4}, {N, N, N, 4, 5, 0, 6}, {2, 3, N, N, 4, 6, 0} }; for (int i = 0; i < vertex.length; i++) Arrays.fill(pre[i], i); floyd(); show(); } public static void floyd() { int len; for (int k = 0; k < matrix.length; k++) for (int i = 0; i < matrix.length; i++) for (int j = 0; j < matrix.length; j++) { len = matrix[i][k] + matrix[k][j]; if (len < matrix[i][j]) { matrix[i][j] = len; pre[i][j] = pre[k][j]; } } } public static void show() { for (int k = 0; k < matrix.length; k++) { for (int i = 0; i < matrix.length; i++) System.out.print(vertex[pre[k][i]] + " "); System.out.println(); for (int i = 0; i < matrix.length; i++) System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + matrix[k][i] + ") "); System.out.println(); } } }
