Arctic Network

From Progteam

Revision as of 04:41, 11 March 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.



Arctic Network
Problem Number 2349
Sorter: hjfreyer
Source: Waterloo local 2002.09.28
Link: 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++)
		edges.add(new Edge(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++)
	    forest.add(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));
    }

    public void add(T t){
	parent.put(t,t);
	sets++;
    }
}

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