poj 3723 Conscription 最小生成树 Java

poj 3723 Conscription
买一个人就可以利用一个关系（一条边），一开始买一个人肯定是要10000的，然后再买一个人就可以根据他之前买的那个人的关系进行减价，相当于一共买n个人的话，是利用到n - 1 条边，所以要构建最大生成树。然后每个人都要基本的10000块，所以答案就是每个人10000 然后减去最大生成树里的所有边的权重。

package 图论;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.PriorityQueue;public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int nextInt() throws IOException {
    st.nextToken();return (int)st.nval;}public static void main(String[] args) throws IOException {
    int t = nextInt();while (t-- > 0) {
    int n = nextInt(); // n 个女兵int m = nextInt(); // m 个男兵int r = nextInt(); // 相当于 r 条边PriorityQueue<Edge> pq = new PriorityQueue<Edge>();for (int i = 0; i < r; i++) {
    int v = nextInt(); // 女兵编号int w = nextInt() + n; // 注意：男兵编号要往后延，这里加的是 nint weight = nextInt(); // 男兵和女兵之间的关系Edge e = new Edge(v, w, weight);pq.add(e);}Kruskal kru = new Kruskal(n + m, pq);int ans = 0;for (Edge e : kru.queue) {
    ans += e.weight;}System.out.println(10000 * (n + m) - ans);}}
}class Edge implements Comparable<Edge> {
    int v;int w;double weight;public Edge(int v, int w, double weight) {
    this.v = v;this.w = w;this.weight = weight;}// 返回边的其中一个顶点int either() {
    return v;}// 返回与v不同的另一个顶点int other(int v) {
    if (v == this.w) {
    return this.v;}return this.w;}@Overridepublic int compareTo(Edge o) {
    return Double.compare(o.weight, this.weight);}
}class UnionFind {
    int[] parent;int[] size; // 根结点对应的分量的大小int count; // 连通分量的数量public UnionFind(int n) {
    parent = new int[n];size = new int[n];for (int i = 0; i < n; i++) {
    parent[i] = i;}for (int i = 0; i < n; i++) {
    size[i] = 1;}count = n;}int find(int p) {
    while (parent[p] != p) {
    p = parent[p];}return p;}boolean isConnected(int p, int q) {
    return find(p) == find(q);}void union(int p, int q) {
    int pRoot = find(p);int qRoot = find(q);if (pRoot == qRoot) {
    return;}// 让小的指向大的if (size[pRoot] < size[qRoot]) {
    parent[pRoot] = qRoot;size[qRoot] += size[pRoot];}else {
    parent[qRoot] = pRoot;size[pRoot] += size[qRoot];}count--;}
}class Kruskal {
    ArrayDeque<Edge> queue;  // 存放最小生成树中的边PriorityQueue<Edge> pq;int ver; // 顶点数public Kruskal(int ver, PriorityQueue<Edge> pq) {
    queue = new ArrayDeque<Edge>();this.ver = ver;this.pq = pq;UnionFind uf = new UnionFind(ver);while (! pq.isEmpty() && queue.size() < ver - 1) {
    Edge e = pq.poll();int v = e.either();int w = e.other(v);if (uf.isConnected(v, w)) {
    continue;}uf.union(v, w);queue.add(e);}}
}