并查集变形——美团笔试

小美的送花路线

https://www.nowcoder.com/questionTerminal/a9980f73060545ca923344098750af18?f=discussion

可以转换成图论，以花店为中心，骑手肯定会选择最长路径只需走一次，其他短路径走两次的方案，这样才能保证实际走的路程最短。
使用并查集将有路径的两个节点相连起来，再构建最长路径。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        UnionFind uf = new UnionFind(n);
        int u, v, w;
        for(int i = 0; i < n - 1; i++){
            String[] params = br.readLine().trim().split(" ");
            u = Integer.parseInt(params[0]);
            v = Integer.parseInt(params[1]);
            w = Integer.parseInt(params[2]);
            uf.union(u, v, w);
        }
        //构建这个最长路径
        uf.buildLongestPath();
        //总路程，实际走的路程
        int totalPath = 0, distance = 0;
        for(int i = 0; i < uf.rank.length; i++){
            if(i == 0)
                continue;
            //总路程是每个客户家到花店的距离
            totalPath += uf.rank[i];
            //如果是最长路径的，走一次就可以了。
            if(uf.longestPath.contains(i)){
                distance += uf.rank[i] - uf.rank[uf.parent[i]];

            }else{    //不是最长路径的，走两次。
                distance += 2 * (uf.rank[i] - uf.rank[uf.parent[i]]);
            }
        }
        System.out.println(totalPath + " " + distance);
    }
}


class UnionFind{
    public int[] parent;    //存放i的父节点
    public int[] rank;      //距离父节点的距离
    public int maxDisIdx = 1;    //最远的那个节点
    public int maxDis = 0;    //最远的距离
    public HashSet<Integer> longestPath;    //将最远的那条路经过的节点记录下来

    public UnionFind(int n){
        parent = new int[n + 1];
        rank = new int [n + 1];
        for(int i = 1; i <= n; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }

    //合并u,v 两个节点
    public void union(int u, int v, int w){
        parent[v] = u;
        rank[v] = rank[u] + w;    //rank求的就是当前节点到最终父节点的距离
        if(rank[v] > maxDis){    //更新最远距离
            maxDis = rank[v];
            maxDisIdx = v;    //记录最远的那个节点
        }
    }

    //构建最长路径
    public void buildLongestPath(){
        longestPath = new HashSet<>();
        int node = maxDisIdx;
        while(node != 1){    //最远的一条路中记录到花店前的所有节点
            longestPath.add(node);
            node = parent[node];
        }
    }   
}

小团的配送团队

https://www.nowcoder.com/questionTerminal/13218137bf64448d9ef485ca219377bf?f=discussion

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.TreeMap;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        UnionFind uf = new UnionFind(n);
        int a, b;
        for(int i = 0; i < m; i++){
            params = br.readLine().trim().split(" ");
            a = Integer.parseInt(params[0]);
            b = Integer.parseInt(params[1]);
            uf.union(a, b);
        }
        // 先输出小区数
        System.out.println(uf.count);
        // 再输出每个小区的订单号 key是放在该小区内编号最小的订单
        TreeMap<Integer, ArrayList<Integer>> region = new TreeMap<>();
        ArrayList<Integer> temp;
        //这里学习一下，放入region里
        for(int i = 1; i <= n; i++){
            if(region.containsKey(uf.parent[i]))
                temp = region.get(uf.parent[i]);
            else
                temp = new ArrayList<>();
            temp.add(i);
            region.put(uf.parent[i], temp);
        }
        //再输出结果
        for(int id: region.keySet()){
            temp = region.get(id);
            for(int i = 0; i < temp.size(); i++)
                System.out.print(temp.get(i) + " ");
            System.out.println();
        }
    }
}

class UnionFind {
    public int[] parent;
    public int count;
    public UnionFind(int n) {
        count = n;
        parent = new int[n + 1];
        for(int i = 1; i <= n; i++){
            parent[i] = i;
        }
    }

    public int find(int x) {
        while(parent[x] != x){
            // 路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    //关键在union方法
    public void union(int x, int y) {
        if(x == y) return;
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY) return;

        // 将节点编号大的合并到节点编号小的节点下面
        if(rootX < rootY){
            for(int i = 0; i < parent.length; ++i){
                if(parent[i] == rootY)
                    parent[i] = rootX;
            }
        }else{
            for(int i = 0; i < parent.length; ++i) {
                if(parent[i] == rootX)
                    parent[i] = rootY;
            }
        }
        count --;
    }
}