2493318_ac_281ms_1116k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>

int m;
int map[501][501];
int B[501], link[501];

struct node
{
	int a, b, c, d;
	int tt;
}taxi[501];

int find(int v)
{
	int i;

	for(i = 1; i <= m; i++)
		if(map[v][i]&&!B[i])
		{
			B[i] = 1;
			if(!link[i]||find(link[i]))
			{
				link[i] = v;
				return 1;
			}
		}
	return 0;
}

void input()
{
	int i, j, tt;
	int hh, mm, ans;

	scanf("%d",&m);
	for(i = 1; i <= m; i++)
	{
		scanf("%d:%d%d%d%d%d",&hh,&mm,&taxi[i].a,&taxi[i].b,&taxi[i].c,&taxi[i].d);
		tt = hh*60+mm;
		taxi[i].tt = tt;
	}
	memset(map,0,sizeof(map));
	for(i = 1; i < m; i++)
		for(j = i+1; j <= m; j++)
			if(taxi[i].tt+abs(taxi[i].a-taxi[i].c)+abs(taxi[i].b-taxi[i].d)+abs(taxi[i].c-taxi[j].a)+abs(taxi[i].d-taxi[j].b)<taxi[j].tt)
				map[i][j] = 1;
	ans = 0;
	memset(link,0,sizeof(link));
	for(i = 1; i <= m; i++)
	{
		memset(B,0,sizeof(B));
		ans += find(i);
	}
	printf("%d\n",m-ans);
}

int main()
{
	int n;

	scanf("%d",&n);
	while(n--)
		input();
	return 0;
}