Guest User

Untitled

a guest
Jul 18th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.79 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.StringTokenizer;
  3.  
  4. public class AlgoMSTB {
  5. public static void main(String[] args) throws IOException{new AlgoMSTB().run();
  6. }
  7. PrintWriter pw;
  8. StringTokenizer st;
  9. BufferedReader br;
  10. public void run() throws IOException {
  11. br=new BufferedReader(new FileReader("spantree.in"));
  12. pw = new PrintWriter(new File("spantree.out"));
  13. st=new StringTokenizer(br.readLine());
  14. int N=Integer.parseInt(st.nextToken());
  15. Element[] Adj=new Element[N+1];
  16. for (int i=1; i<N+1; i++){
  17. st = new StringTokenizer(br.readLine());
  18. int x1=Integer.parseInt(st.nextToken());
  19. int y1=Integer.parseInt(st.nextToken());
  20. Adj[i]=new Element(x1, y1);
  21.  
  22. }
  23. Prim(Adj, N, 1);
  24. pw.println(sum);
  25. br.close();
  26. pw.close();
  27. }
  28. class Element{
  29. int x, y;
  30. Element(int x, int y){
  31. this.x=x;
  32. this.y=y;
  33. }
  34. }
  35.  
  36. enum Color{WHITE,GRAY,BLACK};
  37. Color[] colors=new Color[5002];
  38.  
  39. double d[]=new double[5002];
  40. int u;
  41. double sum=0;
  42. int p[]=new int[5002];
  43. void Prim(Element[] Adj, int N, int s){
  44. for (int i=1; i<N+1; i++) {
  45. if (i!=s) {
  46. d[i]=Double.MAX_VALUE;
  47. }else d[i]=0;
  48. colors[i]=Color.WHITE;
  49. p[i]=-1;
  50. }
  51. for (int i=1; i<N+1; i++){
  52. double min=Double.MAX_VALUE;
  53. for (int k=1; k<N+1; k++)
  54. if ((d[k]<min)&&(colors[k]!=Color.BLACK)){
  55. u=k;
  56. min=d[k];
  57. }
  58. colors[u]=Color.BLACK;
  59. for (int j=1; j<N+1; j++){
  60. if (j!=u){
  61. double destin=Math.hypot(Adj[u].x-Adj[j].x, Adj[u].y-Adj[j].y);
  62. if ((d[j]>destin)&&(colors[j]==Color.WHITE)) {
  63. d[j]=destin;
  64. p[j]=u;
  65. }
  66. }
  67. }
  68. if ( p[u]!=-1) sum=sum+Math.hypot(Adj[u].x-Adj[p[u]].x, Adj[u].y-Adj[p[u]].y);
  69. }
  70.  
  71. }
  72.  
  73.  
  74. }
Add Comment
Please, Sign In to add comment