• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 洛谷 P1967 货车运输 java实现

2周前 (04-30) 6次浏览

https://www.luogu.com.cn/problem/P1967

`for (int j = 1; j <= maxLevel; j++) {    for (int i = 1; i <= n; i++) {        parentInfo[i][j] = parentInfo[parentInfo[i][j - 1]][j - 1];        parentMinWeightInfo[i][j] = Math.min(parentMinWeightInfo[i][j-1],parentMinWeightInfo[parentInfo[i][j - 1]][j - 1]);    }}`

``````import java.io.BufferedReader;
import java.io.FileInputStream;
import java.util.*;

public class Main {
static int[] p, level;
static PriorityQueue<int[]> pq;
static boolean[] isVisit;
static int[][] parentInfo,parentMinWeightInfo;
static int maxLevel,n,m;

public static void main(String[] args) throws Exception {
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

p = new int[n + 1];
pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[2] - o1[2];
}
});
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int from, to, weight;

for (int i = 1; i <= m; i++) {
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
weight = Integer.parseInt(st.nextToken());
}

for (int i = 0; i < adj.length; i++) {
}

int[] edge;
while (!pq.isEmpty()) {
edge = pq.poll();
from = edge[0];
to = edge[1];
weight = edge[2];
if (!connect(from, to)) {
union(from, to);
}
}

isVisit = new boolean[n + 1];
level = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (!isVisit[i]) {
dfs(i,0);
}
}
maxLevel = 0;
for (int i = 1; i <= n; i++) {
maxLevel = Math.max(maxLevel, level[i]);
}
int temp = 0;
while ((1 << temp) < maxLevel) {
temp++;
}
maxLevel = temp;
parentInfo = new int[n + 1][maxLevel + 1];
parentMinWeightInfo = new int[n + 1][maxLevel + 1];

isVisit = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
if (!isVisit[i]) {
parentMinWeightInfo[i][0] = Integer.MAX_VALUE;
dfs2(i);
}
}

for (int j = 1; j <= maxLevel; j++) {
for (int i = 1; i <= n; i++) {
parentInfo[i][j] = parentInfo[parentInfo[i][j - 1]][j - 1];
parentMinWeightInfo[i][j] = Math.min(parentMinWeightInfo[i][j-1],parentMinWeightInfo[parentInfo[i][j - 1]][j - 1]);
}
}

StringBuilder bu = new StringBuilder();
int q = Integer.parseInt(st.nextToken());
int a, b;
for (int i = 0; i < q; i++) {
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
if(!connect(a,b)){
bu.append(-1) ;
if(i != q-1){
bu.append("n");
}
continue;
}
int ans = LCA(a,b);
bu.append(ans) ;
if(i != q-1){
bu.append("n");
}
}
System.out.println(bu.toString());
}

private static void dfs(int from,int deep) {
isVisit[from] = true;
level[from] = ++deep;
for (int[] next : adj[from]) {
if (!isVisit[next[0]]) {
dfs(next[0],deep);
}
}
}

private static void dfs2(int from){
isVisit[from] = true;
for (int[] next : adj[from]) {
if (!isVisit[next[0]]) {
parentMinWeightInfo[next[0]][0] = next[1];
parentInfo[next[0]][0] = from;
dfs2(next[0]);
}
}
}

private static int LCA(int a, int b){
if(level[a]<level[b]){
int temp =a;
a = b;
b = temp;
}
int ans = Integer.MAX_VALUE;
for(int i = maxLevel;i>=0;i--){
if(level[parentInfo[a][i]]>=level[b]){
ans = Math.min(ans, parentMinWeightInfo[a][i]);
a = parentInfo[a][i];
}
}
if(a == b){
return ans;
}
for(int i = maxLevel;i>=0;i--){
if(parentInfo[a][i]!=parentInfo[b][i]){
ans = Math.min(ans,Math.min(parentMinWeightInfo[a][i],parentMinWeightInfo[b][i]));
a = parentInfo[a][i];
b = parentInfo[b][i];
}
}
ans = Math.min(ans,Math.min(parentMinWeightInfo[a][0],parentMinWeightInfo[b][0]));
return ans;
}

private static int find(int a) {
if (p[a] == a) {
return p[a];
}
return p[a] = find(p[a]);
}

private static void union(int a, int b) {
int A = find(a);
int B = find(b);
p[A] = B;
}

private static boolean connect(int a, int b) {
return find(a) == find(b);
}
}
``````