某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全地区畅通需要的最低成本。

输入格式:

输入的第一行给出村庄数目N (1≤N≤100)；随后的N(N−1)/2行对应村庄间道路的成本及修建状态：每行给出4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态 — 1表示已建，0表示未建。

输出格式:

输出全省畅通需要的最低成本。

输入样例:

4

1 2 1 1

1 3 4 0

1 4 1 1

2 3 3 0

2 4 2 1

3 4 5 0

输出样例:

3

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

import java.io.*;
import java.util.*;

// 表示一条道路（边）
class Edge implements Comparable<Edge> {
    int village1;
    int village2;
    int cost;

    public Edge(int v1, int v2, int cost) {
        this.village1 = v1;
        this.village2 = v2;
        this.cost = cost;
    }

    // 用于 Kruskal 算法中的排序
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.cost, other.cost);
    }
}

public class Main {
    // 并查集数组
    static int[] parent;

    // 查找根节点（带路径压缩）
    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 合并两个集合
    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int totalEdges = N * (N - 1) / 2;

        // 初始化并查集
        parent = new int[N + 1]; // 索引 1 到 N
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        // 存储所有边
        List<Edge> edges = new ArrayList<>();

        // 读取每条道路信息
        for (int i = 0; i < totalEdges; i++) {
            String[] parts = br.readLine().split("\\s+");
            int v1 = Integer.parseInt(parts[0]);
            int v2 = Integer.parseInt(parts[1]);
            int cost = Integer.parseInt(parts[2]);
            int status = Integer.parseInt(parts[3]);

            // 如果道路已修建 (status == 1)，则成本为 0
            if (status == 1) {
                cost = 0;
            }

            edges.add(new Edge(v1, v2, cost));
        }

        // 按成本升序排序
        Collections.sort(edges);

        int totalCost = 0;
        int edgesSelected = 0; // 已选择的边数

        // Kruskal 算法
        for (Edge edge : edges) {
            if (edgesSelected == N - 1) break; // 最小生成树完成

            int root1 = find(edge.village1);
            int root2 = find(edge.village2);

            if (root1 != root2) {
                // 两个村庄不在同一连通分量，选择这条边
                union(root1, root2);
                totalCost += edge.cost;
                edgesSelected++;
            }
        }

        // 输出最低成本
        System.out.println(totalCost);
    }
}