gopherii.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 104 行

package PKU.Hungary;
import java.util.*;
/**
 * ID:2536
 * 匈牙利算法
 * @author yhm
 *
 */
public class GopherII {

	
	static int n,m,s,v;
	static int[] link;
	static boolean[] use;
	static boolean[][] array;
	static int size;
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			n = cin.nextInt();
			m = cin.nextInt();
			s = cin.nextInt();
			v = cin.nextInt();
			GopherIIPoint[] gophers = new GopherIIPoint[n];
			for(int i=0;i<n;i++){
				gophers[i] = new GopherIIPoint(cin.nextDouble(),cin.nextDouble());
			}
			GopherIIPoint[] holes = new GopherIIPoint[m];
			for(int i=0;i<m;i++){
				holes[i] = new GopherIIPoint(cin.nextDouble(),cin.nextDouble());
			}
			
			init(gophers, holes);
			
			int num=0;
			for(int i=0;i<size;i++){
				Arrays.fill(use, false);
				if(can(i)){
					num++;
				}
			}
			
			
			System.out.println(n-num);
		}

	}
	
	static boolean can(int i){
		
		for(int j=0;j<size;j++){
			if(!use[j] && array[i][j]){
				use[j] = true;
				if(link[j]==-1 || can(link[j])){
					link[j] = i;
					return true;
				}
			}
		}
		
		return false;
	}
	
	static void init(GopherIIPoint[] gophers, GopherIIPoint[] holes){
		size = n+m;
		array = new boolean[size][size];
		link = new int[size];
		Arrays.fill(link, -1);
		use = new boolean[size];
		
		double safe = s*v;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				double dis = gophers[i].getDistance(holes[j]);
				if(dis<=safe){
					array[i][j+n] = true;
				}
			}
		}
	}

}

class GopherIIPoint{
	double x;
	double y;
	public GopherIIPoint(double x, double y) {
		super();
		this.x = x;
		this.y = y;
	}
	
	public double getDistance(GopherIIPoint p){
		double dis = (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
		dis = Math.sqrt(dis);
		return dis;
	}
	
}