Poj Solution 1287

http://poj.org/problem?id=1287

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Edge implements Comparable{
    int start,end;
    int cost;
    public int compareTo(Object temp){
        Edge cnt = (Edge) temp;
        if(cnt.cost< this.cost) return 1;
        return -1;
    }
}
class Set{
    final int N = 100;
    int father[] = new int[N],num[] = new int[N];
    void init(){
        for(int i=0;i< N;++i){
            father[i] = -1;
            num[i] = 0;
        }
    }
    int find(int who){
        int u,v = who;
        while(this.father[who]!=-1){
            who = this.father[who];
        }
        while(v!=who){
            u = this.father[v];
            this.father[v] = who;
            v = u;
        }
        return who;
    }
    void set(int a,int b){
        a = this.find(a);
        b = this.find(b);
        if(a==b)
            return ;
        if(this.num[a]>this.num[b]){
            this.father[b] = a;
            this.num[a]+=this.num[b];
        }else{
            this.father[a] = b;
            this.num[b]+=this.num[a];
        }
    }
}
public class Main {
    static final int N = 100000;
    static int n,m;
    static Set set = new Set();
    static Edge edge[] = new Edge[N];
    static void start(){
        for(int i=0;i< N;++i)
            edge[i] = new Edge();
    }
    static int solve(){
        int ans=0;
        int i;
        Arrays.sort(edge,0,m);
        for(i=0;i< m;++i){
            if(set.find(edge[i].start)!=set.find(edge[i].end))
                ans+=edge[i].cost;
            set.set(edge[i].start, edge[i].end);
        }
        return ans;
    }
public static void main(String[]args) throws Exception{
 int i,j;
 start();
 StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
 while(true){
    n = Get_Num(cin);
    if(n==0) break;
    m = Get_Num(cin);
    set.init();
    for(i=0;i< m;++i){
        edge[i].start = Get_Num(cin);
        edge[i].end = Get_Num(cin);
        edge[i].cost = Get_Num(cin);
    }
    System.out.println(solve());
  }
}
    static int Get_Num(StreamTokenizer cin)throws Exception{
        cin.nextToken();
        return (int)cin.nval;
    }
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *