gopher ii(二分匹配).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

#define NMAX 110
int n,m,s,v;
struct node {
	double x,y;
}go[NMAX], hole[NMAX];
bool path[NMAX][NMAX];
bool flag[NMAX];
int match[NMAX];

inline double dist(node & p1, node & p2)
{
	return sqrt(1.0*(p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

bool dfs(int pos)
{
	int i;
	for(i=0;i<m;i++) {
		if(path[pos][i] && !flag[i]) {
			int pre = match[i];
			match[i] = pos;
			flag[i] = true;
			if(pre == -1 || dfs(pre)) {
				return true;
			}
			match[i] = pre;
		}
	}
	return false;
}

int Max_Match()
{
	int i,mmax = 0;
	memset(match,-1,sizeof(match));
	for(i=0;i<n;i++) {
		memset(flag,false,sizeof(flag));
		if( dfs(i) ) {
			mmax ++;
		}
	}
	return mmax;
}

int main()
{
	int i,j;
	while(scanf("%d %d %d %d", &n,&m,&s,&v)==4) {
		for(i=0;i<n;i++) {
			scanf("%lf %lf", &go[i].x, &go[i].y);
		}
		for(i=0;i<m;i++) {
			scanf("%lf %lf", &hole[i].x, &hole[i].y);
		}
		memset(path,0,sizeof(path));
		for(i=0;i<n;i++) {
			for(j=0;j<m;j++) {
				double ct = dist(go[i], hole[j]) / v;
				if(ct+1e-8 <= s) {
					path[i][j] = true;
				}
			}
		}
		printf("%d\n", n - Max_Match());
	}
}