# Arctic Network

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by hjfreyer.

 Sorter: hjfreyer Waterloo local 2002.09.28 http://acm.pku.edu.cn/JudgeOnline/problem?id=2349

Arctic Network is problem number 2349 on the Peking University ACM site. Compare with Out of Hay.

## Solution

The solution is basically to find the longest edge in an MST. Only the satellite edges let you exclude the S most expensive edges from the MST. The code below uses a modified Kruskal's Algorithm to find the longest edge required.

## Code

```
import java.util.*;

public class Main{

public static Scanner in;

public static void main(String[] args){
in=new Scanner(System.in);

doStuff();
}

public static void doStuff(){
int N=in.nextInt();

for(int i=0;i<N;i++){
solve();
}
}

public static void solve(){
int S=in.nextInt();
int P=in.nextInt();

int[] xs=new int[P];
int[] ys=new int[P];

for(int j=0;j<P;j++){
xs[j]=in.nextInt();
ys[j]=in.nextInt();
}

final double[][] dist=new double[P][P];

for(int i=0;i<P;i++){
for(int j=0;j<=i;j++){
if(j==i){
dist[i][j]=Double.POSITIVE_INFINITY;
} else {
double d=distform(xs[i],
ys[i],
xs[j],
ys[j]);

dist[i][j]=d;
dist[j][i]=d;
}
}
}

// Dist now has the distances between the points

List<Edge> edges=new ArrayList<Edge>();

for(int i=0;i<P;i++)
for(int j=0;j<i;j++)

Collections.sort(edges, new Comparator<Edge>(){
public int compare(Edge e1, Edge e2){
if(dist[e1.i][e1.j] < dist[e2.i][e2.j])
return -1;
if(dist[e1.i][e1.j] == dist[e2.i][e2.j])
return 0;
if(dist[e1.i][e1.j] > dist[e2.i][e2.j])
return 1;
throw new AssertionError();
}
});

//	for(Edge e: edges)
//  System.out.printf("%d, %d: %f\n",e.i,e.j,dist[e.i][e.j]);

DisjointSet<Integer> forest=new DisjointSet<Integer>();
for(int i=0;i<P;i++)

Edge largest=null;

for(Edge e:edges){
if(forest.sets==S)
break;

largest=e;

forest.union(e.i,e.j);
//   System.out.printf("%d: %.2f\n",forest.sets,dist[e.i][e.j]);
}

double res=dist[largest.i][largest.j];
System.out.printf("%.2f\n",Math.round(100.0*res)/100.0);
}
public static double distform(int x1,int y1, int x2,int y2){
double dx=x2-x1;
double dy=y2-y1;

return Math.sqrt(Math.pow(dx,2)+Math.pow(dy,2));
}
}

class DisjointSet<T> {
HashMap<T,T> parent;
Random rand;
int sets=0;

public DisjointSet(){
rand=new Random();
parent=new HashMap<T,T>();
}

public void union(T a, T b){
if(a.equals(b))
return;
if(parent.get(a).equals(a) && parent.get(b).equals(b)){
if(rand.nextBoolean())
parent.put(b,a);
else
parent.put(a,b);
sets--;
return;
}
union(find(a),find(b));
}

public T find(T x){
if(parent.get(x).equals(x))
return x;
T p=find(parent.get(x));
parent.put(x,p);

return p;
}

public boolean equal(T a, T b){
return find(a).equals(find(b));
}

parent.put(t,t);
sets++;
}
}

class Edge{
int i,j;
public Edge(int i,int j){
this.i=i;this.j=j;
}
}
```