D - Built? AtCoder Beginner Contest 065 - バイトの競プロメモ

D - Built?

問題概略

N個の街があり、座標(x,y)が与えられる

座標 $(a, b)$ にある街と座標 $(c, d)$ にある街の間に道を造るのには、 $m i n (| a - c |, | b - d |)$ 円かかります、最小全域木

制約

$2 ≦ N ≦ 10^{5}$
$0 ≦ x_{i}, y_{i} ≦ 10^{9}$
入力は全て整数である

解法

隣り合わない街をつないでも意味がないと気づく。

x,yについて隣り合うところに辺を追加して全域木

@SuppressWarnings("unchecked")
public class Main
{
    
    static FastScanner sc = new FastScanner(System.in);
    static int N;
    static ArrayList<Edge> edges = new ArrayList<>();
    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        P[] px = new P[N];
        P[] py = new P[N];
        for (int i = 0; i < N; i++)
        {
            px[i] = new P(sc.nextInt(), i);
            py[i] = new P(sc.nextInt(), i);
        }
        Arrays.sort(px);
        Arrays.sort(py);
        for (int i = 0; i < N - 1; i++)
        {
            addEdge(px[i].id, px[i + 1].id, px[i + 1].v - px[i].v);
            addEdge(py[i].id, py[i + 1].id, py[i + 1].v - py[i].v);
        }
        Collections.sort(edges);

        //クラスカル法
        UnionFindTree uni = new UnionFindTree(N);
        long res = 0;
        for (Edge e : edges)
        {
            int f = e.f;
            int t = e.t;
            if (uni.isSame(f, t)) continue;
            uni.unite(f, t);
            res += e.toCost;
        }
        System.out.println(res);
    }


    public static void addEdge(int f, int t, long c)
    {
        edges.add(new Edge(f, t, c));
    }


    static class Edge implements Comparable<Edge>
    {
        int f;
        int t;
        long toCost;

        Edge(int f, int to, long cost)
        {
            this.f = f;
            t = to;
            toCost = cost;
        }

        @Override
        public int compareTo(Edge e)
        {
            return toCost == e.toCost ? 0 : toCost > e.toCost ? 1 : -1;
        }

    }
class UnionFindTree
{
    int[] par;
    int[] rank;
    int[] sizes;

    UnionFindTree(int n)
    {
        par = new int[n];
        rank = new int[n];
        sizes = new int[n];
        for (int i = 0; i < n; i++)
        {
            par[i] = i;
            sizes[i] = 1; 
        }
    }

    int root(int x)
    {
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);

        if (rx == ry) return;
        if (rank[rx] < rank[ry])
        {
            par[rx] = ry;
            sizes[ry] += sizes[rx];
        }
        else
        {
            par[ry] = rx;
            sizes[rx] += sizes[ry];
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
    }

    boolean isSame(int x, int y)
    {
        return root(x) == root(y);
    }

    int size(int x)
    {
        return sizes[root(x)];
    }
}

class P implements Comparable<P>
{
    int v, id;

    P(int a, int b)
    {
        v = a;
        id = b;
    }

    @Override
    public boolean equals(Object o)
    {
        if (this == o) return true;
        if (!(o instanceof P)) return false;
        P p = (P) o;
        return v == p.v && id == p.id;
    }

    @Override
    public int hashCode()
    {
        return Objects.hash(v, id);
    }

    @Override
    public int compareTo(P p)
    {
        return v == p.v ? id - p.id : v - p.v; //xで昇順にソート
        //return (v == p.v ? id - p.id : v - p.v) * -1; //xで降順にソート
        //return id == p.id ? v - p.v : id - p.id;//yで昇順にソート
        //return (id == p.id ? v - p.v : id - p.id)*-1;//yで降順にソート
    }
}