Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.StringTokenizer;
- public class AlgoMSTB {
- public static void main(String[] args) throws IOException{new AlgoMSTB().run();
- }
- PrintWriter pw;
- StringTokenizer st;
- BufferedReader br;
- public void run() throws IOException {
- br=new BufferedReader(new FileReader("spantree.in"));
- pw = new PrintWriter(new File("spantree.out"));
- st=new StringTokenizer(br.readLine());
- int N=Integer.parseInt(st.nextToken());
- Element[] Adj=new Element[N+1];
- for (int i=1; i<N+1; i++){
- st = new StringTokenizer(br.readLine());
- int x1=Integer.parseInt(st.nextToken());
- int y1=Integer.parseInt(st.nextToken());
- Adj[i]=new Element(x1, y1);
- }
- Prim(Adj, N, 1);
- pw.println(sum);
- br.close();
- pw.close();
- }
- class Element{
- int x, y;
- Element(int x, int y){
- this.x=x;
- this.y=y;
- }
- }
- enum Color{WHITE,GRAY,BLACK};
- Color[] colors=new Color[5002];
- double d[]=new double[5002];
- int u;
- double sum=0;
- int p[]=new int[5002];
- void Prim(Element[] Adj, int N, int s){
- for (int i=1; i<N+1; i++) {
- if (i!=s) {
- d[i]=Double.MAX_VALUE;
- }else d[i]=0;
- colors[i]=Color.WHITE;
- p[i]=-1;
- }
- for (int i=1; i<N+1; i++){
- double min=Double.MAX_VALUE;
- for (int k=1; k<N+1; k++)
- if ((d[k]<min)&&(colors[k]!=Color.BLACK)){
- u=k;
- min=d[k];
- }
- colors[u]=Color.BLACK;
- for (int j=1; j<N+1; j++){
- if (j!=u){
- double destin=Math.hypot(Adj[u].x-Adj[j].x, Adj[u].y-Adj[j].y);
- if ((d[j]>destin)&&(colors[j]==Color.WHITE)) {
- d[j]=destin;
- p[j]=u;
- }
- }
- }
- if ( p[u]!=-1) sum=sum+Math.hypot(Adj[u].x-Adj[p[u]].x, Adj[u].y-Adj[p[u]].y);
- }
- }
- }
Add Comment
Please, Sign In to add comment