2942147_ac_500ms_4872k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main {
    
    static int n, m;
    static double s, v;
    static boolean map[][] = new boolean [101][101];
    static boolean b[] = new boolean [101];
    static int link[] = new int [101];
    
    public static int dfs(int v)
    {
        int i;
        
        for(i = 1; i <= m; i++)
        {
            if(map[v][i]&&!b[i])
            {
                b[i] = true;
                if(link[i]==0||dfs(link[i])==1)
                {
                    link[i] = v;
                    return 1;
                }
            }
        }
        return 0;
    }
    
    public static double dis(double x,double y,double x1, double y1)
    {
        return Math.sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
    }
    
    public static void main(String[] args) {
        
        Scanner cin = new Scanner (System.in);
        int i, j;
        double pos[][] = new double [101][2];
        double x, y, d;
        
        while(cin.hasNext())
        {
            n = cin.nextInt();
            m = cin.nextInt();
            s = cin.nextDouble();
            v = cin.nextDouble();
            for(i = 1; i <= n; i++)
            {
                pos[i][0] = cin.nextDouble();
                pos[i][1] = cin.nextDouble();
                for(j = 1; j <= m; j++)
                    map[i][j] = false;
            }
            for(i = 1; i < 101; i++)
                link[i] = 0;
            for(i = 1; i <= m; i++)
            {
                x = cin.nextDouble();
                y = cin.nextDouble();
                for(j = 1; j <= n; j++)
                {
                    d = dis(x,y,pos[j][0],pos[j][1]);
                    if(d/v<=s)
                    {
                        map[j][i] = true;
                    }
                }
            }
            int ans = 0;
            for(i = 1; i <= n; i++)
            {
                for(j = 1; j < 101; j++)
                    b[j] = false;
                ans += dfs(i);
            }
            System.out.println(n-ans);
        }
    }
}