Guest User

Untitled

a guest
Jul 18th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.01 KB | None | 0 0
  1. /*
  2. * wrote by Alex Vikharev
  3. * 21.11.2009
  4. */
  5.  
  6. import java.io.BufferedReader;
  7. import java.io.BufferedWriter;
  8. import java.io.FileReader;
  9. import java.io.FileWriter;
  10. import java.io.IOException;
  11. import java.util.Arrays;
  12. import java.util.Comparator;
  13. import java.util.StringTokenizer;
  14.  
  15. public class mindiff implements Runnable {
  16.  
  17. private String nextToken() {
  18. if (st == null || !st.hasMoreTokens()) {
  19. try {
  20. st = new StringTokenizer(in.readLine());
  21. } catch (IOException e) {
  22. e.printStackTrace();
  23. }
  24. }
  25. return st.nextToken();
  26. }
  27.  
  28. private int nextInt() {
  29. return new Integer(nextToken());
  30. }
  31.  
  32. private long nextLong() {
  33. return new Long(nextToken());
  34. }
  35.  
  36. class DSU {
  37.  
  38. int parent[];
  39. int rank[];
  40.  
  41. public DSU(int size) {
  42. parent = new int[size];
  43. for (int i = 0; i < size; i++) {
  44. parent[i] = i;
  45. }
  46. rank = new int[size];
  47. }
  48.  
  49. private void join(int x, int y) {
  50. if (rank[x] > rank[y]) {
  51. parent[y] = x;
  52. } else {
  53. parent[x] = y;
  54. if (rank[x] == rank[y])
  55. ++rank[y];
  56. }
  57. }
  58.  
  59. public void unite(int x, int y) {
  60. join(get(x), get(y));
  61. }
  62.  
  63. private int get(int a) {
  64. if (parent[a] != parent[parent[a]]) {
  65. parent[a] = get(parent[a]);
  66. }
  67. return parent[a];
  68. }
  69.  
  70. public boolean isInOneSet(int a, int b) {
  71. return get(a) == get(b);
  72. }
  73.  
  74. }
  75.  
  76. private StringTokenizer st;
  77. private BufferedReader in;
  78. private BufferedWriter out;
  79.  
  80. class Edge {
  81. public int a;
  82. public int b;
  83. public int w;
  84.  
  85. public Edge(int a, int b, int w) {
  86. super();
  87. this.a = a;
  88. this.b = b;
  89. this.w = w;
  90. }
  91.  
  92. }
  93.  
  94. @Override
  95. public void run() {
  96. try {
  97. in = new BufferedReader(new FileReader("mindiff.in"));
  98. out = new BufferedWriter(new FileWriter("mindiff.out"));
  99.  
  100. int N = nextInt();
  101. int M = nextInt();
  102.  
  103. Edge[] edge = new Edge[M];
  104. for (int i = 0; i < M; i++) {
  105. edge[i] = new Edge((nextInt() - 1), (nextInt() - 1), nextInt());
  106. }
  107.  
  108. Arrays.sort(edge, new Comparator<Edge>() {
  109.  
  110. @Override
  111. public int compare(Edge arg0, Edge arg1) {
  112. return arg0.w - arg1.w;
  113. }
  114.  
  115. });
  116.  
  117. int diff = Integer.MAX_VALUE;
  118.  
  119. for (int k = 0; k <= M - N + 1; k++) {
  120.  
  121. DSU dsu = new DSU(N);
  122. int min = edge[k].w;
  123. int max = 0;
  124. for (int i = k; i < M; i++) {
  125. if (!dsu.isInOneSet(edge[i].a, edge[i].b)) {
  126. dsu.unite(edge[i].a, edge[i].b);
  127. max = edge[i].w;
  128. }
  129. }
  130.  
  131. boolean isTree = true;
  132. for (int i = 0; i < N-1; i++) {
  133. if (!dsu.isInOneSet(i, i+1)) {
  134. isTree = false;
  135. break;
  136. }
  137. }
  138.  
  139. if(isTree && diff > (max - min)){
  140. diff = max - min;
  141. }
  142.  
  143. }
  144.  
  145. if(diff == Integer.MAX_VALUE){
  146. out.write("NO\n");
  147. } else {
  148. out.write("YES\n" + diff + "\n");
  149. }
  150.  
  151.  
  152. in.close();
  153. out.close();
  154. } catch (Exception e) {
  155. // TODO Auto-generated catch block
  156. e.printStackTrace();
  157. }
  158. }
  159.  
  160. public static void main(String[] args) {
  161. new Thread(new mindiff()).start();
  162. }
  163.  
  164. }
Add Comment
Please, Sign In to add comment