SRM 278 DIV1 Hard UnitsMoving

問題 Editorial

問題

略

解答

二分探索*二部マッチング。
mid以下の時間でたどり着ける位置同士に辺を張って、完全マッチングが出来るかどうかで判定する

コード

#include <string>
#include <vector>
#include <sstream>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
using namespace std;

vector<bool> done;
vector<int> match;
vector<vector<int> >e;
bool augment(int i) {
	if(done[i]) return false;
	else done[i] = true;
	each(j, e[i]) if(match[*j] == -1 || augment(match[*j])) {
		match[*j] = i;
		return true;
	}
	return false;
}

struct UnitsMoving {
	double bestTime(vector <string> start, vector <string> finish) {
		int n = start.size();
		static double sx[55], sy[55], v[55], fx[55], fy[55];
		rep(i, n) { stringstream ss(start[i]); ss >> sx[i] >> sy[i] >> v[i]; }
		rep(i, n) { stringstream ss(finish[i]); ss >> fx[i] >> fy[i]; }
		double l = 0, u = 100000;
		rep(ii, 100) {
			double m = (l + u) / 2;
			e = vector<vector<int> >(n);
			rep(i, n) rep(j, n)
			if(hypot(sx[i] - fx[j], sy[i] - fy[j]) / v[i] <= m) {
				e[i].pb(j);
			}
			match = vector<int>(n, -1);
			int count = 0;
			rep(i, n) {
				done = vector<bool>(n, false);
				if(augment(i)) ++ count;
			}
			(count == n ? u : l) = m;
		}
		return l;
	}
};