[NOI题库][POJ2536][匈牙利算法][二分图最大匹配]Gopher II

#include <stdio.h>
#include <math.h>
#include <string.h>
struct location{
    double x, y;
    int belong;
}hole[ 110 ], gopher[ 110 ];

bool line[ 110 ][ 110 ]; // line[ gopher ][ hole ];
int n, m, s, v;
double maxd;
bool used[ 110 ];
int ans = 0;

double dis( double x1, double y1, double x2, double y2)
{
    return ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 );
}

bool find( int x )
{
    int i;
    for( i = 1; i <= m; i++ ){
        if( line[ x ][ i ] && !used[ i ] ){
            used[ i ] = true;
            if( hole[ i ].belong == 0 || find( hole[ i ].belong ) ){
                hole[ i ].belong = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{


    while( scanf("%d%d%d%d", &n, &m, &s, &v) != EOF ){
        memset( hole, 0, sizeof( hole ));
        memset( gopher, 0, sizeof( gopher ));
        memset( line, 0, sizeof( line ));
        ans = 0;
        int i, j, k;

        maxd = v * s * v * s;
        /* gopher */
        for( i = 1; i <= n; i++ )
            scanf("%lf%lf", &gopher[ i ].x, &gopher[ i ].y);

        /* hole */
        for( i = 1; i <= m; i++ ){
            scanf("%lf%lf", &hole[ i ].x, &hole[ i ].y);
            for( j = 1; j <= n; j++ ){
                if( dis( hole[ i ].x, hole[ i ].y, gopher[ j ].x, gopher[ j ].y) <= maxd ){
                    /* AddEdge */
                    line[ j ][ i ] = true;
                }
            }
        }

        for( i = 1; i <= n; i++ ){
            memset( used, 0, sizeof( used ));
            if( find( i ) ) ans++;
        }

        printf("%d\n", n - ans);

    }
    return 0;
}