本文主要是介绍最小生成树的应用模板（普利姆算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
代码无误，空间爆了，纯属洛谷责任
P1396 营救 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码：
import java.awt.Checkbox;
import java.awt.PageAttributes.OriginType;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;import javax.print.attribute.standard.JobMessageFromOperator;
import javax.print.attribute.standard.MediaName;
import javax.print.attribute.standard.ReferenceUriSchemesSupported;import java.awt.Checkbox;
import java.awt.PageAttributes.OriginType;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;import javax.print.attribute.standard.JobMessageFromOperator;
public class Main {
public static void main(String[] args) throws IOException {Scanner sc=new Scanner(System.in);BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br1.readLine().split(" ");
nn=Integer.parseInt(aStrings[0]);
mm=Integer.parseInt(aStrings[1]);
ss=Integer.parseInt(aStrings[2]);
tt=Integer.parseInt(aStrings[3]);
int a;
int u,v,w;
GG=new int[nn+1][nn+1];
closeset=new int[nn+1];
lowcost=new int[nn+1];
qianqu=new int[nn+1];
for(a=0;a<=nn;a++) {Arrays.fill(GG[a], aa);
}
for(a=0;a<mm;a++) {String[] bStrings=br1.readLine().split(" ");u=Integer.parseInt(bStrings[0]);v=Integer.parseInt(bStrings[1]);w=Integer.parseInt(bStrings[2]);GG[v][u]=Math.min(GG[v][u], w);GG[u][v]=Math.min(GG[u][v], w);
}
pirm();
zhuixun(ss, tt);
System.out.println(answer);}public static int nn,mm,ss,tt;public static int[][] GG;public static int[] closeset;public static int[] lowcost;public static int[] qianqu;public static int aa=Integer.MAX_VALUE;public static int answer=0;public static void zhuixun(int x,int y) {if(x==y) {return;}answer=Math.max(answer, lowcost[y]);zhuixun(x, qianqu[y]);}public static void pirm() {int a;for(a=0;a<=nn;a++) {Arrays.fill(closeset, 0);Arrays.fill(lowcost, aa);}int num,e,ans;e=ss;num=0;ans=0;qianqu[e]=e;closeset[e]=-1;while(num<nn-1) {int micost=aa;int miedge=-1;for(int b=1;b<=nn;b++) {if(closeset[b]!=-1) {int temp=GG[e][b];if(GG[e][b]<lowcost[b]) {lowcost[b]=temp;closeset[b]=e;}if(lowcost[b]<micost) {micost=lowcost[b];miedge=b;}}}num++;ans=ans+micost;e=miedge;qianqu[e]=closeset[e];closeset[e]=-1;}}
}核心思想，最小生成树得到后一定使得我们旋定的那个点到其他所有的额点的花费的总和最小。
那如何求解这道题目呢，我们想一下，从s到t的所有路径中，按照上述方法进行的最小路径计算，我们假设从s到t一共经过5条边，因为最小生成树是唯一确定的，所以这5条变一定是唯一确定的，根据最小生成树的原理我们可以得出结论，直接跟t来连接的那条边一定是所有跟t来连接的边的最小的那个，假设这个点是m，因为最小生成树就是找到t与t-1个点的最小边，同理，来连接m的边也一定是所有跟m连接的最小的边，所以有结论，从s到t的路径的最大值就是我们要求的。
在原版pirm算法上，我们首先额外剋一个前驱数组用来记录每个点的前驱点，然后加一个路径寻找方法来搜索路径，就完成啦
这篇关于最小生成树的应用模板（普利姆算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
