【二分图+最大匹配】北大 poj 2536 Gopher II

?

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL   : http://poj.org/problem?id=2536Name  : 2536 Gopher IIDate  : Saturday, November 26, 2011Time Stage : two hoursResult: 9601664panyanyany2536Accepted200K32MSC++1863B2011-11-26 21:19:399601635panyanyany2536Accepted200K47MSC++2275B2011-11-26 21:12:039601633panyanyany2536Time Limit ExceededC++2273B2011-11-26 21:11:479601593panyanyany2536Wrong AnswerC++2190B2011-11-26 21:01:229601586panyanyany2536Wrong AnswerC++2411B2011-11-26 20:58:439601577panyanyany2536Time Limit ExceededC++2409B2011-11-26 20:56:279601530panyanyany2536Time Limit ExceededC++2188B2011-11-26 20:41:34Test Data :Review :犯了一些比较白痴+神经质的错误, 这题其实是比较简单的……//----------------------------------------*/#include <stdio.h>#include <string.h>#include <math.h>#define MAXSIZE108intn, m, s, v ;intlink[MAXSIZE] ;boolcover[MAXSIZE] ;boolgraph[MAXSIZE][MAXSIZE] ;struct POINT {double x, y ;} ;POINTgopher[MAXSIZE], hole[MAXSIZE] ;double dist (int i, int j){double x = abs (gopher[i].x - hole[j].x) ;double y = abs (gopher[i].y - hole[j].y) ;return sqrt (x * x + y * y) ;}void connect (){int i, j ;memset (graph, 0, sizeof (graph)) ;for (i = 1 ; i <= n ; ++i){for (j = 1 ; j <= m ; ++j){if (dist(i, j) <= s * v)graph[i][j] = true ;}}}bool find (int cur){int i ;for (i = 1 ; i <= m ; ++i){if (cover[i] == false && graph[cur][i] == true){cover[i] = true ;if (link[i] == 0 || find (link[i])){link[i] = cur ;return true ;}}}return false ;}int getSum (){int i ;int sum ;sum = 0 ;memset (link, 0, sizeof (link)) ;for (i = 1 ; i <= n ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}return sum ;}int main (){int i, j ;while (scanf ("%d%d%d%d", &n, &m, &s, &v) != EOF){// input gopher's coordinatesfor (i = 1 ; i <= n ; ++i){scanf ("%lf%lf", &gopher[i].x, &gopher[i].y) ;}// input gopher hole's coordinatesfor (i = 1 ; i <= m ; ++i){scanf ("%lf%lf", &hole[i].x, &hole[i].y) ;}connect () ;printf ("%d\n", n - getSum()) ;}return 0 ;}