Guest User

Untitled

a guest
Jul 18th, 2018
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.68 KB | None | 0 0
  1. package graph;
  2.  
  3. import java.io.*;
  4.  
  5. import java.util.StringTokenizer;
  6. import java.util.Arrays;
  7.  
  8. public class Kruskall implements Runnable {
  9.  
  10. class Edge implements Comparable<Edge> {
  11. int v1;
  12. int v2;
  13. int weight;
  14.  
  15. Edge(int v1, int v2, int weight) {
  16. this.v1 = v1;
  17. this.v2 = v2;
  18. this.weight = weight;
  19. }
  20.  
  21. public int compareTo(Edge that) {
  22. if(weight < that.weight) return -1;
  23. if(weight > that.weight) return 1;
  24. return 0;
  25. }
  26. }
  27.  
  28. class DSU {
  29. int[] p;
  30. int[] r;
  31.  
  32. DSU(int n) {
  33. p = new int[n];
  34. r = new int[n];
  35.  
  36. for(int i = 0; i < n; i++) p[i] = i;
  37. }
  38.  
  39. int get(int i) {
  40. if(i != p[i]) {
  41. p[i] = get(p[i]);
  42. }
  43. return p[i];
  44. }
  45.  
  46. void union(int i, int j) {
  47. i = get(i);
  48. j = get(j);
  49.  
  50. if(r[i] == r[j]) r[i]++;
  51.  
  52. if(r[i] < r[j]) p[i] = j;
  53. else p[j] = i;
  54. }
  55. }
  56.  
  57. int n;
  58. int m;
  59.  
  60. Edge[] edges;
  61.  
  62. DSU trees;
  63.  
  64. public void run() {
  65. try {
  66. BufferedReader in = new BufferedReader(new FileReader("mindiff.in"));
  67. PrintWriter out = new PrintWriter("mindiff.out");
  68. StringTokenizer st = new StringTokenizer(in.readLine());
  69.  
  70. n = Integer.parseInt(st.nextToken());
  71. m = Integer.parseInt(st.nextToken());
  72.  
  73. if(n == 1) {
  74. out.println("YES");
  75. out.print(0);
  76. out.close();
  77. }
  78.  
  79. edges = new Edge[m];
  80. trees = new DSU(n + 1);
  81.  
  82. int t1;
  83. int t2;
  84. int t3;
  85.  
  86. for(int i = 0; i < m; i++) {
  87. st = new StringTokenizer(in.readLine());
  88.  
  89. t1 = Integer.parseInt(st.nextToken());
  90. t2 = Integer.parseInt(st.nextToken());
  91. t3 = Integer.parseInt(st.nextToken());
  92.  
  93. edges[i] = new Edge(t1, t2, t3);
  94. }
  95.  
  96. Arrays.sort(edges);
  97.  
  98. Edge e;
  99.  
  100. Edge min;
  101. Edge max;
  102.  
  103. double res = Double.POSITIVE_INFINITY;
  104.  
  105. for(int j = 0; j < m; j++) {
  106.  
  107. min = edges[j];
  108. max = edges[j];
  109.  
  110. trees = new DSU(n + 1);
  111.  
  112. for (int i = 0; i < m; i++) {
  113. e = edges[i];
  114.  
  115. if(e.weight < min.weight) continue;
  116.  
  117. if (trees.get(e.v1) != trees.get(e.v2)) {
  118.  
  119. if(max.weight < e.weight) max = e;
  120.  
  121. trees.union(e.v1, e.v2);
  122. }
  123. }
  124.  
  125. boolean good = true;
  126.  
  127. for(int i = 0; i < m; i++) {
  128. e = edges[i];
  129. if(trees.get(e.v1) != trees.get(e.v2)) {
  130. good = false;
  131. break;
  132. }
  133. }
  134.  
  135. if(good) res = Math.min(res, max.weight - min.weight);
  136.  
  137. }
  138.  
  139. out.println("YES");
  140.  
  141. out.print((int)res);
  142.  
  143. in.close();
  144. out.close();
  145. } catch(Exception e) {
  146. e.printStackTrace();
  147. }
  148. }
  149.  
  150. public static void main(String[] args) {
  151. new Thread(new Kruskall()).start();
  152. }
  153. }
Add Comment
Please, Sign In to add comment