[UVa] 10080 - Gopher II

題目網址: http://goo.gl/5Xdcr7

題 意: 有 n 隻地鼠， m 個地洞，告訴你地鼠、地洞的座標，還有地鼠的速度 v，此時天上有隻老鷹，當老鷹飛下來時，地鼠若無法在 s 時間內跑近地洞，就會被老鷹吃掉，且一個地洞只能容納一隻地鼠，問最後能有幾隻地鼠會被攻擊。


解法: 分成地鼠與地洞兩個集合，地鼠要配地洞，很明顯就是二分匹配(bipartite matching)唷，只要符合地鼠到地洞的距離小於等於 s * v，就把該地鼠與該地洞建邊，接著用 bipartite matching 演算法就可解。

TAG: Bipartite Matching

注意:

程式碼:

	/**
	* Tittle: 10080 - Gopher II
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/18
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	#define EPS 1e-8
	class Point {
	public:
	double x, y;
	Point( double _x = 0, double _y = 0 ): x(_x), y(_y) {}
	};
	// declarations
	int n, m;
	double s, v;
	bool edge[N][N];
	Point gopher[N];
	Point hole[N];
	// functions
	int dcmp( double x )
	{
	if( x < -EPS ) return -1; return x > EPS;
	}
	int pre[N];
	bool vis[N];
	const bool path( int u )
	{
	FOR( i, 1, m ) if( edge[u][i] && !vis[i] ) {
	vis[i] = true;
	if( !pre[i] || path(pre[i]) ) {
	pre[i] = u;
	return true;
	}
	}
	return false;
	}
	const int maxMatch( void )
	{
	static int ret;
	ret = 0;
	clr( pre, 0 );
	FOR( i, 1, n ) {
	clr( vis, false );
	if( path(i) ) ++ret;
	}
	return ret;
	}
	double dis( const Point &a, const Point &b )
	{
	double dx = a.x-b.x;
	double dy = a.y-b.y;
	return sqrt( dx*dx + dy*dy );
	}
	// main function
	int main( void )
	{
	double far;
	// input
	while( scanf( "%d%d%lf%lf", &n, &m, &s, &v )==4 ) {
	FOR( i, 1, n ) scanf( "%lf%lf", &gopher[i].x, &gopher[i].y );
	FOR( i, 1, m ) scanf( "%lf%lf", &hole[i].x, &hole[i].y );
	far = s*v;
	clr( edge, false );
	// solve & output
	FOR( i, 1, n ) FOR( j, 1, m ) {
	if( dcmp( dis(gopher[i],hole[j])-far ) <= 0 )
	edge[i][j] = true;
	}
	printf( "%d\n", n-maxMatch() );
	}
	return 0;
	}

view raw 10080 - Gopher II.cpp hosted with ❤ by GitHub