UVa 10080 Gopher II

題意：
    有N個地鼠和M個地鼠洞，每個點都有座標(x,y)，因此每隻地鼠和每個地鼠洞之間有不同的距離，每隻地鼠的移動速度都是v，現在有老鷹會在s秒後抓沒有跑進洞的地鼠，一個地鼠洞只能藏一隻地鼠，求沒有躲到洞裡被老鷹抓走的地鼠的最少數量為?

想法：
    地鼠在左邊，地鼠洞在右邊，把每隻地鼠與能在時間內跑到的地鼠洞都建一條邊，然後做最大匹配，答案就是(地鼠數量-最大匹配數)。

	#include <cstdio>
	#include <cstdlib>
	#include <cmath>
	#include <algorithm>
	struct Point{
	double x;
	double y;
	};
	bool edge[105][105];
	int llink[105], rlink[105];
	bool used[105];
	bool DFS(int now, const int &m);
	int main(int argc, char ** argv)
	{
	system(argv[0]);
	int n, m, s, v;
	Point gopher[105], hole[105];
	while (scanf("%d %d %d %d", &n, &m, &s, &v) == 4) {
	// Input
	for (int i = 0; i < n; ++i) scanf("%lf %lf", &gopher[i].x, &gopher[i].y);
	for (int i = 0; i < m; ++i) scanf("%lf %lf", &hole[i].x, &hole[i].y);
	// Distance
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j) {
	double dis = sqrt(pow(gopher[i].x-hole[j].x,2)+pow(gopher[i].y-hole[j].y,2));
	if (dis/v <= s) edge[i][j] = true;
	else edge[i][j] = false;
	}
	// Bipartite
	int ans = 0;
	std::fill(llink, llink+n, -1);
	std::fill(rlink, rlink+m, -1);
	for (int i = 0; i < n; ++i) {
	std::fill(used, used+m, false);
	if (DFS(i, m)) ++ans;
	}
	printf("%d\n", n-ans);
	}
	}
	bool DFS(int now, const int &m)
	{
	for (int nxt = 0; nxt < m; ++nxt) {
	if (edge[now][nxt] == false || used[nxt]) continue;
	used[nxt] = true;
	if (rlink[nxt] == -1 || DFS(rlink[nxt], m)) {
	llink[now] = nxt;
	rlink[nxt] = now;
	return true;
	}
	}
	return false;
	}

view raw [UVa] 10080 Gopher II hosted with ❤ by GitHub