백준 2191 / C++

https://www.acmicpc.net/problem/2191

2191번: 들쥐의 탈출

 

[ 풀이 ] 

거리가 SV 이하면 연결해주고 최대매칭을 구해주면 됩니다. 답은 N-최대매칭 이 되겠네요. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
struct pdd {
	double x, y;
};
vector<int>g[111];
double s, v;
int n, m, par[111], vis[111];
pdd a[101], h[101];

double dist(pdd a, pdd b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int match(int x) {
	for (int nx : g[x]) {
		if (vis[nx])continue;
		vis[nx] = 1;
		if (!~par[nx] || match(par[nx])) {
			par[nx] = x;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> s >> v;
	for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
	for (int i = 1; i <= m; i++) cin >> h[i].x >> h[i].y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (dist(a[i], h[j]) <= s * s * v * v) {
				g[i].push_back(j);
			}
		}
	}
	int ans = n;
	memset(par, -1, sizeof(par));
	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		ans -= match(i);
	}
	cout << ans;
}