1708.cpp

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

/* This Code is Submitted by wywcgs for Problem 1708 on 2006-11-09 at 19:14:40 */
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
const int N = 512;
const int INF = 1 << 28;
 
class Taxi {
public:
	int bt, et, x1, y1, x2, y2;
	void make();
	bool next(const Taxi& t) const { return t.bt-et > abs(x2-t.x1)+abs(y2-t.y1); }
};
void Taxi::make() {
	int h, m; scanf("%d:%d %d %d %d %d", &h, &m, &x1, &y1, &x2, &y2);
	bt = h*60+m; et = bt+abs(x2-x1)+abs(y2-y1);
}

class Graph {
private:
	vector<int> g[N];
	int ns, nt, xmate[N], ymate[N], ds[N], dt[N], dis;
	bool vst[N];
	bool search();
	bool dfs(int);
public:
	int getNode() const { return nt; }
	void build();
	int match();
};
void Graph::build() {
	Taxi taxi[N];
	int n; scanf("%d", &n);
	ns = nt = n;
	for(int i = 0; i < n; i++) { taxi[i].make(); g[i].clear(); }
	for(int i = 0; i < n; i++)
		for(int j = i+1; j < n; j++)
			if(taxi[i].next(taxi[j])) g[i].push_back(j);
}
bool Graph::search() {
	memset(ds, -1, sizeof(ds)); memset(dt, -1, sizeof(dt));
	queue<int> Q; dis = INF;
	for(int i = 0; i < ns; i++)
		if(xmate[i] == -1) { Q.push(i); ds[i] = 0; }
	while(!Q.empty()) {
		int u = Q.front(); Q.pop();
		if(ds[u] > dis) break;
		for(int i = g[u].size()-1; i >= 0; i--) {
			int v = g[u][i];
			if(dt[v] != -1) continue;
			dt[v] = ds[u]+1;
			if(ymate[v] == -1) dis = dt[v];
			else { ds[ymate[v]] = dt[v]+1; Q.push(ymate[v]); }
		}
	}
	return (dis != INF);
}
bool Graph::dfs(int u) {
	for(int i = g[u].size()-1; i >= 0; i--) {
		int v = g[u][i];
		if(vst[v] || dt[v] != ds[u]+1) continue;
		int ut = ymate[v], vs = xmate[u];
		vst[v] = true;
		if(ut != -1 && dt[v] == dis) continue;
		ymate[v] = u; xmate[u] = v;
		if(ut == -1 || dfs(ut)) return true;
		ymate[v] = ut; xmate[u] = vs;
	}
	return false;
}
int Graph::match() {
	int mth = 0;
	memset(xmate, -1, sizeof(xmate)); memset(ymate, -1, sizeof(ymate));
	while(search()) {
		memset(vst, false, sizeof(vst));
		for(int i = 0; i < ns; i++)
			if(ds[i] == 0 && dfs(i)) mth++;
	}
	return mth;
}

Graph g;

int main()
{
	int T;
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		g.build();
		printf("%d\n", g.getNode()-g.match());
	}
	
	return 0;
}