最小生成树1（Prim模板）、最小生成树2（kruskal模板）、最近公共祖先（模板）

最小生成树1模板问题描述给定一个包含 nn 个顶点和 mm 条边的无向图。图中可能存在重边和自环且边的权值可能为负数。你需要求出最小生成树MST的边权重之和。如果无法构造最小生成树则输出 impossible。最小生成树在一个无向图中由 nn 个顶点和 n−1n−1 条边构成的连通子图且该子图的边权重之和最小。如果图不连通无法形成最小生成树。输入格式第一行输入二个正整数 n,mn,m。接下来 mm 行每行输入 33 个正整数 a,b,ca,b,c。表示点 aa 到点 bb 存在一条无向边权值为 cc。2≤n≤500,1≤m≤105,1≤a,b≤n,1≤c≤1042≤n≤500,1≤m≤105,1≤a,b≤n,1≤c≤104。输出格式输出一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。样例输入4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4样例输出6import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static int n,m; static int id1; static int dist[]new int[N]; static boolean isSure[]new boolean[N]; static int h[]new int[N]; static int e[]new int[N]; static int ne[]new int[N]; static int w[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); mInteger.parseInt(st.nextToken()); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()); int bInteger.parseInt(st.nextToken()); int cInteger.parseInt(st.nextToken()); add(a,b,c);add(b,a,c); } Arrays.fill(dist, Integer.MAX_VALUE); dist[1]0; PriorityQueueNode priorityQueuenew PriorityQueueNode(); priorityQueue.add(new Node(1,0)); int cnt0;//一共选中几个点了 int res0; while(cntn !priorityQueue.isEmpty()){ Node nopriorityQueue.poll(); int uno.x; if(!isSure[u]){ resdist[u]; isSure[u]true;cnt; for (int i h[u]; i 0; ine[i]) { int sone[i]; if(!isSure[son]){ if(dist[son]w[i]){//这里表示的是到选中的集合的距离 dist[son]w[i]; priorityQueue.add(new Node(son,dist[son])); } } } } } if(cnt!n){ bw.write(impossible); }else{ bw.write(res); } br.close(); bw.flush(); bw.close(); } static class Node implements ComparableNode{ int x; int dis; public Node() {} public Node(int x, int dis) { this.x x; this.dis dis; } Override public int compareTo(Node o) { // TODO Auto-generated method stub return this.dis-o.dis; } } static void add(int a,int b,int c){ e[id]b; ne[id]h[a]; w[id]c; h[a]id; } }最小生成树2模板给定一个包含 nn 个顶点和 mm 条边的无向图。图中可能存在重边和自环且边的权值可能为负数。你需要求出最小生成树MST的边权重之和。如果无法构造最小生成树则输出 impossible。最小生成树在一个无向图中由 nn 个顶点和 n−1n−1 条边构成的连通子图且该子图的边权重之和最小。如果图不连通无法形成最小生成树。输入格式第一行输入二个正整数 n,mn,m。接下来 mm 行每行输入 33 个正整数 a,b,ca,b,c。表示点 aa 到点 bb 存在一条无向边权值为 cc。2≤n≤105,1≤m≤2×105,1≤a,b≤n,1≤c≤1042≤n≤105,1≤m≤2×105,1≤a,b≤n,1≤c≤104。输出格式输出一行若存在最小生成树则输出一个整数表示最小生成树的树边权重之和如果最小生成树不存在则输出 impossible。样例输入4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4样例输出6​import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static int n,m; static int id1; static Node node[]new Node[N]; static int p[]new int[N];//并查集判断有没有环 static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); mInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { p[i]i; } PriorityQueueNode priorityQueuenew PriorityQueue(); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()); int bInteger.parseInt(st.nextToken()); int cInteger.parseInt(st.nextToken()); priorityQueue.add(new Node(a,b,c)); } int cnt0;//边数 int res0; while(cntn !priorityQueue.isEmpty()){ Node nopriorityQueue.poll(); int ano.a,bno.b,cno.dis; if(find(a)!find(b)){ resc;cnt; union(a,b); } } if(cntn-1){ bw.write(res); }else{ bw.write(impossible); } br.close(); bw.flush(); bw.close(); } static void union(int a,int b){ int pafind(a),pbfind(b); p[pa]pb; } static int find(int u){ if(u!p[u]){ p[u]find(p[u]); } return p[u]; } static class Node implements ComparableNode{ int a; int b; int dis; public Node() { // TODO Auto-generated constructor stub } public Node(int a, int b, int dis) { this.a a; this.b b; this.dis dis; } Override public int compareTo(Node o) { // TODO Auto-generated method stub return dis-o.dis; } } }最近公共祖先模板问题描述给定一棵有 NN 个节点的树每个节点有一个唯一的编号从 11 到 NN。树的根节点是 11 号节点。接下来你会得到 QQ 个查询。对于每个查询你将得到两个节点的编号你的任务是找到这两个节点的最低公共祖先。输入格式第一行包含一个整数 NN表示树的节点数。接下来的 N−1N−1 行每行包含两个整数 UU 和 VV表示节点 UU 和节点 VV 之间有一条边。下一行包含一个整数 QQ表示查询的数量。接下来的 QQ 行每行包含两个整数 AA 和 BB表示你需要找到节点 AA 和节点 BB 的最低公共祖先。输出格式对于每个查询输出一行该行包含一个整数表示两个节点的最近公共祖先。样例输入5 1 2 1 3 2 4 2 5 3 4 5 3 4 3 5样例输出2 1 1样例说明对于第一个查询44 和 55 的最低公共祖先是 22。对于第二个查询33 和 44 的最低公共祖先是 11。对于第三个查询33 和 55 的最低公共祖先是 11。测评数据规模2≤N≤1052≤N≤1051≤Q≤1041≤Q≤1041≤U,V,A,B≤N1≤U,V,A,B≤N题目保证输入的边形成一棵树。​import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static int n,m; static int id1; static int log2[]new int[N1]; static int dep[]new int[N]; static int f[][]; static int h[]new int[N]; static int e[]new int[N]; static int ne[]new int[N]; static int w[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); int uInteger.parseInt(st.nextToken()),vInteger.parseInt(st.nextToken()); add(u,v);add(v,u); } log2[1]0; for (int i 2; i N; i) { log2[i]log2[i/2]1; } mlog2[N-1]; fnew int[N][m1]; dfs(1,0); stnew StringTokenizer(br.readLine()); int qInteger.parseInt(st.nextToken()); for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int uInteger.parseInt(st.nextToken()),vInteger.parseInt(st.nextToken()); if(uv)bw.write(u); else{ if(dep[u]dep[v]){//设定u的深度更大 int tu;uv;vt; } for (int j m-1; j 0; j--) { if(dep[f[u][j]]dep[v])uf[u][j]; } if(uv){ bw.write(u\n); }else{ for (int j m-1; j 0; j--) { if(f[u][j]!f[v][j]){ uf[u][j]; vf[v][j]; } } bw.write(f[u][0]\n); } } } br.close(); bw.flush(); bw.close(); } static void dfs(int u,int p){ dep[u]dep[p]1; f[u][0]p; //2^(i)2^(i-1)2^(i-1) for (int i 1; i m; i) { f[u][i]f[f[u][i-1]][i-1]; } for (int i h[u]; i0; ine[i]) { int sone[i]; if(sonp)continue; dfs(son, u); } } static void add(int a,int b){ e[id]b; ne[id]h[a]; h[a]id; } }