908- Re-Connecting ... Can' find the mistake (Java)

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Ackdari
New poster
Posts: 1
Joined: Tue Jan 26, 2016 12:32 am

908- Re-Connecting ... Can' find the mistake (Java)

Post by Ackdari » Tue Jan 26, 2016 12:56 am

Hello to all of you...

I have a working solution for this problem or at least I haven't found any test Case which producess a woring answer according to uDebug. But if I submit it to the onlineJudge it says worng answer.

So please could someone have a look on my code or give me some critical Input to find the mistake on my own.

Here is my code:

Code: Select all

import java.util.Scanner;
import java.util.List;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Main{

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        StringBuilder out = new StringBuilder();
        PriorityQueue<Connection> connections = new PriorityQueue<Connection>();
        boolean first = true;

        while(in.hasNextInt()){
            Clustors clusores = new Clustors();
            int n, oldCost = 0, k, newCost = 0;	

            n = in.nextInt();
            if(!first)
                out.append("\n");

            for(int i=0; i < n-1; i++){
                in.nextInt(); in.nextInt();
                oldCost += in.nextInt();
            }

            for(int i=0; i < 2; i++){
                k = in.nextInt();
                for(int j=0; j < k; j++){
                    int u = in.nextInt();
                    int v = in.nextInt();
                    int kosten = in.nextInt();
                    if(u != v){
                        Connection c = new Connection(u, v, kosten);
                        connections.add(c);
                    }
                }
            }

            while(!connections.isEmpty()){
                Connection c = connections.poll();
                if(!clusores.isSameCluster(c.u, c.v)){
                    newCost += c.kosten;
                    clusores.add(c.u, c.v);
                }
            }

            out.append(oldCost + "\n" + newCost + "\n");
            first = false;
        }
        System.out.print(out);
    }

    //------------
    private static class Connection implements Comparable<Connection>{
        private final int u;
        private final int v;
        private final int kosten;

        public Connection(int v, int u, int kosten){
            this.u = u;
            this.v = v;
            this.kosten = kosten;
        }

        public int compareTo(Connection c){
            if(kosten > c.kosten)
                return 1;
            else
                return -1;
        }

    }

    private static class Clustors{

        private HashSet<HashSet<Integer>> clustors;

        private Clustors(){
            clustors = new HashSet<HashSet<Integer>>();
        }

        private boolean isSameCluster(int u, int v){
            for(HashSet<Integer> set : clustors){
                if(set.contains(u) && set.contains(v))
                    return true;
            }
            return false;
        }

        public void add(int v, int u){
            HashSet<Integer> uCluster = null , vCluster = null;
            for(HashSet<Integer> set : clustors){
                if(set.contains(v))
                    vCluster = set;
                else if(set.contains(u))
                    uCluster = set;
            }
            if(uCluster != null && vCluster != null){
                for(int i : vCluster){
                    uCluster.add(i);
                }
                clustors.remove(vCluster);
            }else if(uCluster == null && vCluster == null){
                HashSet<Integer> newCluster = new HashSet<Integer>();
                newCluster.add(v);
                newCluster.add(u);
                clustors.add(newCluster);
            }else{
                if(uCluster == null)
                    uCluster = vCluster;
                uCluster.add(v);
                uCluster.add(u);
            }
        }

    }

}
MfG
Ackdari

Post Reply

Return to “Volume 9 (900-999)”