Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package graph;
- import java.io.*;
- import java.util.StringTokenizer;
- import java.util.Arrays;
- public class Kruskall implements Runnable {
- class Edge implements Comparable<Edge> {
- int v1;
- int v2;
- int weight;
- Edge(int v1, int v2, int weight) {
- this.v1 = v1;
- this.v2 = v2;
- this.weight = weight;
- }
- public int compareTo(Edge that) {
- if(weight < that.weight) return -1;
- if(weight > that.weight) return 1;
- return 0;
- }
- }
- class DSU {
- int[] p;
- int[] r;
- DSU(int n) {
- p = new int[n];
- r = new int[n];
- for(int i = 0; i < n; i++) p[i] = i;
- }
- int get(int i) {
- if(i != p[i]) {
- p[i] = get(p[i]);
- }
- return p[i];
- }
- void union(int i, int j) {
- i = get(i);
- j = get(j);
- if(r[i] == r[j]) r[i]++;
- if(r[i] < r[j]) p[i] = j;
- else p[j] = i;
- }
- }
- int n;
- int m;
- Edge[] edges;
- DSU trees;
- public void run() {
- try {
- BufferedReader in = new BufferedReader(new FileReader("mindiff.in"));
- PrintWriter out = new PrintWriter("mindiff.out");
- StringTokenizer st = new StringTokenizer(in.readLine());
- n = Integer.parseInt(st.nextToken());
- m = Integer.parseInt(st.nextToken());
- if(n == 1) {
- out.println("YES");
- out.print(0);
- out.close();
- }
- edges = new Edge[m];
- trees = new DSU(n + 1);
- int t1;
- int t2;
- int t3;
- for(int i = 0; i < m; i++) {
- st = new StringTokenizer(in.readLine());
- t1 = Integer.parseInt(st.nextToken());
- t2 = Integer.parseInt(st.nextToken());
- t3 = Integer.parseInt(st.nextToken());
- edges[i] = new Edge(t1, t2, t3);
- }
- Arrays.sort(edges);
- Edge e;
- Edge min;
- Edge max;
- double res = Double.POSITIVE_INFINITY;
- for(int j = 0; j < m; j++) {
- min = edges[j];
- max = edges[j];
- trees = new DSU(n + 1);
- for (int i = 0; i < m; i++) {
- e = edges[i];
- if(e.weight < min.weight) continue;
- if (trees.get(e.v1) != trees.get(e.v2)) {
- if(max.weight < e.weight) max = e;
- trees.union(e.v1, e.v2);
- }
- }
- boolean good = true;
- for(int i = 0; i < m; i++) {
- e = edges[i];
- if(trees.get(e.v1) != trees.get(e.v2)) {
- good = false;
- break;
- }
- }
- if(good) res = Math.min(res, max.weight - min.weight);
- }
- out.println("YES");
- out.print((int)res);
- in.close();
- out.close();
- } catch(Exception e) {
- e.printStackTrace();
- }
- }
- public static void main(String[] args) {
- new Thread(new Kruskall()).start();
- }
- }
Add Comment
Please, Sign In to add comment