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);
}
}
}
}
Ackdari