1353.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1353 on 2006-02-18 at 19:47:29 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int INF = 1 << 30;

class Point {
public:
	int x, y;
	void make();
	double dis(const Point&) const;
};
void Point::make() {
	scanf("%d %d", &x, &y);
}
double Point::dis(const Point& p) const {
	return sqrt(1.0*(x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));
}

class Plane {
public:
	int time, speed, b;
	void make();
};
void Plane::make() {
	int h, m;
	scanf("%d %d %d %*d %d", &h, &m, &b, &speed); 
	time = h * 3600 + m * 60; b--;
}

class Edge {
public:
	double time;
	int plane, tower;
	void make(int, int, const Plane&, double);
	bool operator <(const Edge&) const;
};
void Edge::make(int b, int e, const Plane& p, double d) {
	time = p.time + d / p.speed;
	plane = b; tower = e;
}
bool Edge::operator <(const Edge& e) const {
	return time < e.time;
}

int n, k, p, d;
bool used[MAX][MAX], check[MAX];
int match[MAX];

bool D_Match();
bool DFS(int);

int main()
{
	Point port[MAX], tower[MAX];
	Plane plane[MAX];
	Edge e[MAX*MAX];
	int i, j;

	while(scanf("%d %d %d %d", &n, &k, &p, &d) != EOF && n != 0) {
		for(i = 0; i < n; i++) port[i].make();
		for(i = 0; i < k; i++) tower[i].make();
		for(i = 0; i < p; i++) plane[i].make();
		if(d > k || d > p) printf("Impossible!\n");
		else {
			int en = 0; n = max(p, k);
			for(i = 0; i < p; i++)
				for(j = 0; j < k; j++)
					e[en++].make(i, j, plane[i], port[plane[i].b].dis(tower[j]));
			sort(e, e+en);
			int per = INF, head = 0;
			memset(used, false, sizeof(used));
			for(i = 0; head != en; i++) {
				while(head != en && !D_Match()) used[e[head].plane][e[head].tower] = true, head++;
				if(head == en && !D_Match()) break;
				per = min(per, (int)(e[head-1].time-e[i].time));
				used[e[i].plane][e[i].tower] = false;
			}
			per = (per + 30) / 60;
			printf("%d:%d\n", per/60, per%60);
		}
	}
	
	return 0;
}

bool D_Match()
{
	int i, hit = 0;
	memset(match, -1, sizeof(match));
	for(i = 0; i < n; i++) {
		memset(check, false, sizeof(check));
		if(DFS(i)) hit++;
		if(hit == d) return true;
	}
	return false;
}
bool DFS(int m)
{
	int i;
	for(i = 0; i < n; i++) {
		if(!check[i] && used[i][m]) {
			check[i] = true;
			int t = match[i];
			match[i] = m;
			if(t == -1 || DFS(t)) return true;
			else match[i] = t;
		}
	}
	return false;
}