Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * wrote by Alex Vikharev
- * 21.11.2009
- */
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.util.Arrays;
- import java.util.Comparator;
- import java.util.StringTokenizer;
- public class mindiff implements Runnable {
- private String nextToken() {
- if (st == null || !st.hasMoreTokens()) {
- try {
- st = new StringTokenizer(in.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- private int nextInt() {
- return new Integer(nextToken());
- }
- private long nextLong() {
- return new Long(nextToken());
- }
- class DSU {
- int parent[];
- int rank[];
- public DSU(int size) {
- parent = new int[size];
- for (int i = 0; i < size; i++) {
- parent[i] = i;
- }
- rank = new int[size];
- }
- private void join(int x, int y) {
- if (rank[x] > rank[y]) {
- parent[y] = x;
- } else {
- parent[x] = y;
- if (rank[x] == rank[y])
- ++rank[y];
- }
- }
- public void unite(int x, int y) {
- join(get(x), get(y));
- }
- private int get(int a) {
- if (parent[a] != parent[parent[a]]) {
- parent[a] = get(parent[a]);
- }
- return parent[a];
- }
- public boolean isInOneSet(int a, int b) {
- return get(a) == get(b);
- }
- }
- private StringTokenizer st;
- private BufferedReader in;
- private BufferedWriter out;
- class Edge {
- public int a;
- public int b;
- public int w;
- public Edge(int a, int b, int w) {
- super();
- this.a = a;
- this.b = b;
- this.w = w;
- }
- }
- @Override
- public void run() {
- try {
- in = new BufferedReader(new FileReader("mindiff.in"));
- out = new BufferedWriter(new FileWriter("mindiff.out"));
- int N = nextInt();
- int M = nextInt();
- Edge[] edge = new Edge[M];
- for (int i = 0; i < M; i++) {
- edge[i] = new Edge((nextInt() - 1), (nextInt() - 1), nextInt());
- }
- Arrays.sort(edge, new Comparator<Edge>() {
- @Override
- public int compare(Edge arg0, Edge arg1) {
- return arg0.w - arg1.w;
- }
- });
- int diff = Integer.MAX_VALUE;
- for (int k = 0; k <= M - N + 1; k++) {
- DSU dsu = new DSU(N);
- int min = edge[k].w;
- int max = 0;
- for (int i = k; i < M; i++) {
- if (!dsu.isInOneSet(edge[i].a, edge[i].b)) {
- dsu.unite(edge[i].a, edge[i].b);
- max = edge[i].w;
- }
- }
- boolean isTree = true;
- for (int i = 0; i < N-1; i++) {
- if (!dsu.isInOneSet(i, i+1)) {
- isTree = false;
- break;
- }
- }
- if(isTree && diff > (max - min)){
- diff = max - min;
- }
- }
- if(diff == Integer.MAX_VALUE){
- out.write("NO\n");
- } else {
- out.write("YES\n" + diff + "\n");
- }
- in.close();
- out.close();
- } catch (Exception e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- public static void main(String[] args) {
- new Thread(new mindiff()).start();
- }
- }
Add Comment
Please, Sign In to add comment