問題描述

試題編號： 201412-4
試題名稱： 最優(yōu)灌溉
時間限制： 1.0s
內(nèi)存限制： 256.0MB
問題描述：
　　雷雷承包了很多片麥田，為了灌溉這些麥田，雷雷在第一個麥田挖了一口很深的水井，所有的麥田都從這口井來引水灌溉。
　　為了灌溉，雷雷需要建立一些水渠，以連接水井和麥田，雷雷也可以利用部分麥田作為“中轉(zhuǎn)站”，利用水渠連接不同的麥田，這樣只要一片麥田能被灌溉，則與其連接的麥田也能被灌溉。
　　現(xiàn)在雷雷知道哪些麥田之間可以建設(shè)水渠和建設(shè)每個水渠所需要的費用（注意不是所有麥田之間都可以建立水渠）。請問灌溉所有麥田最少需要多少費用來修建水渠。
輸入格式
　　輸入的第一行包含兩個正整數(shù)n, m，分別表示麥田的片數(shù)和雷雷可以建立的水渠的數(shù)量。麥田使用1, 2, 3, ……依次標號。
　　接下來m行，每行包含三個整數(shù)ai, bi, ci，表示第ai片麥田與第bi片麥田之間可以建立一條水渠，所需要的費用為ci。
輸出格式
　　輸出一行，包含一個整數(shù)，表示灌溉所有麥田所需要的最小費用。
樣例輸入
4 4
1 2 1
2 3 4
2 4 2
3 4 3
樣例輸出
6
樣例說明
　　建立以下三條水渠：麥田1與麥田2、麥田2與麥田4、麥田4與麥田3。
評測用例規(guī)模與約定
　　前20%的評測用例滿足：n≤5。
　　前40%的評測用例滿足：n≤20。
　　前60%的評測用例滿足：n≤100。
　　所有評測用例都滿足：1≤n≤1000，1≤m≤100,000，1≤ci≤10,000。

題解

直接套模板即可

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;

public class csp_2014_12_4 {

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        
        Tri[] tris = new Tri[m];
        int num = 0;
        while (num != m) {
            in.nextToken();
            int u = (int) in.nval;
            in.nextToken();
            int v = (int) in.nval;
            in.nextToken();
            int w = (int) in.nval;
            tris[num ++] = new Tri(u, v, w);
        }
        
        Comparator<Tri> cmp = new Comparator<Tri>() {
            public int compare(Tri t1, Tri t2) {
                return t1.val - t2.val;
            }
        };
        Arrays.sort(tris, 0, m, cmp);
        
        Unionx uset = new Unionx(n);
        int cost = 0;
        num = 0;
        for (int i = 0; i < m; i ++) {
            int x = uset.find(tris[i].begin);
            int y = uset.find(tris[i].end);
            if (x != y) {
                num ++;
                uset.unionx(x, y);
                cost += tris[i].val;
            }
            if (num == n) {
                break;
            }
        }
        System.out.println(cost);
    }
    
    static class Unionx {
        int[] f;
        public Unionx(int n) {
            this.f = new int[n + 5];
            for (int i = 1; i <= n; i ++) {
                f[i] = i;
            }
        }
        
        public int find(int x) {
            return f[x] == x ? x : find(f[x]);
        }
        
        public void unionx(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                f[x] = y;
            }
        }
    }
    
    static class Tri {
        int begin;
        int end;
        int val;
        public Tri(int begin, int end, int val) {
            this.begin = begin;
            this.end = end;
            this.val = val;
        }
    }

}

更多CCF題目代碼可參考：https://github.com/dhwgithub/CCF-CSP-Recording