最小生成树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

样例输出

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 N=2*100010; static int n,m; static int id=1; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); m=Integer.parseInt(st.nextToken()); for (int i = 0; i < m; i++) { st=new StringTokenizer(br.readLine()); int a=Integer.parseInt(st.nextToken()); int b=Integer.parseInt(st.nextToken()); int c=Integer.parseInt(st.nextToken()); add(a,b,c);add(b,a,c); } Arrays.fill(dist, Integer.MAX_VALUE); dist[1]=0; PriorityQueue<Node> priorityQueue=new PriorityQueue<Node>(); priorityQueue.add(new Node(1,0)); int cnt=0;//一共选中几个点了 int res=0; while(cnt<n && !priorityQueue.isEmpty()){ Node no=priorityQueue.poll(); int u=no.x; if(!isSure[u]){ res+=dist[u]; isSure[u]=true;cnt++; for (int i = h[u]; i > 0; i=ne[i]) { int son=e[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 Comparable<Node>{ 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 N=2*100010; static int n,m; static int id=1; static Node node[]=new Node[N]; static int p[]=new int[N];//并查集判断有没有环 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); m=Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) { p[i]=i; } PriorityQueue<Node> priorityQueue=new PriorityQueue<>(); for (int i = 0; i < m; i++) { st=new StringTokenizer(br.readLine()); int a=Integer.parseInt(st.nextToken()); int b=Integer.parseInt(st.nextToken()); int c=Integer.parseInt(st.nextToken()); priorityQueue.add(new Node(a,b,c)); } int cnt=0;//边数 int res=0; while(cnt<n && !priorityQueue.isEmpty()){ Node no=priorityQueue.poll(); int a=no.a,b=no.b,c=no.dis; if(find(a)!=find(b)){ res+=c;cnt++; union(a,b); } } if(cnt==n-1){ bw.write(res+""); }else{ bw.write("impossible"); } br.close(); bw.flush(); bw.close(); } static void union(int a,int b){ int pa=find(a),pb=find(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 Comparable<Node>{ 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≤105，1≤Q≤1041≤Q≤104，1≤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 N=2*100010; static int n,m; static int id=1; static int log2[]=new int[N+1]; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); for (int i = 1; i < n; i++) { st=new StringTokenizer(br.readLine()); int u=Integer.parseInt(st.nextToken()),v=Integer.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; } m=log2[N-1]; f=new int[N][m+1]; dfs(1,0); st=new StringTokenizer(br.readLine()); int q=Integer.parseInt(st.nextToken()); for (int i = 0; i < q; i++) { st=new StringTokenizer(br.readLine()); int u=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken()); if(u==v)bw.write(u+""); else{ if(dep[u]<dep[v]){//设定u的深度更大 int t=u;u=v;v=t; } for (int j = m-1; j >= 0; j--) { if(dep[f[u][j]]>=dep[v])u=f[u][j]; } if(u==v){ bw.write(u+"\n"); }else{ for (int j = m-1; j >= 0; j--) { if(f[u][j]!=f[v][j]){ u=f[u][j]; v=f[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]; i>0; i=ne[i]) { int son=e[i]; if(son==p)continue; dfs(son, u); } } static void add(int a,int b){ e[id]=b; ne[id]=h[a]; h[a]=id++; } }