想看更多的解题报告: http://iyenn.com/rec/1824570.html
                                  转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意:有m个任务，每个任务有开始的时间(xx:xx)，起点(a,b)与终点(c,d)
然后做完这个任务的时间是|a-c|+|b-d|分钟，如果一个车子在一天(00:00 to 23:59)之内做完i任务之后又能
做j任务，那么这个车子就做2个任务，依次类推下去
问最少需要多少辆车子把所有任务都做完

解题思路：最小路径覆盖
建图：i的开始时间+做完i任务的时间+做完i任务的终点到j任务的起点的时间 那么做完i又能做完j，则i指向j

然后求最小路径覆盖即可

/*
Memory 424K
Time  157MS
*/
#include 
using namespace std;
#define MAXV 505
typedef struct{
	int ti;
	int a,b,c,d;
}TEST;
 
TEST t[MAXV];
 
bool map[MAXV][MAXV],use[MAXV];
int n,link[MAXV];
 
int dfs(int cap){
	int i,j;
	for(i=0;i
		if(map[cap][i] && !use[i]){
			use[i]=1;
			j=link[i];
			link[i]=cap;
			if(j==-1 || dfs(j)) return true;
			link[i]=j;
		}
		return false;
}
 
int hungary(){
	int i,num=0;
	memset(link,-1,sizeof(link));
	for(i=0;i
		memset(use,0,sizeof(use));
		if(dfs(i)) num++;
	}
	return n-num;
}
 
bool pd(int x,int y){
	if(x==y) return 0;
	int tmp=abs(t[x].a-t[x].c)+abs(t[x].b-t[x].d)+t[x].ti;		//做x任务的时间+x任务开始的时间
	tmp+=abs(t[x].c-t[y].a)+abs(t[x].d-t[y].b);				//做完x任务再做y任务的时间
	if(tmpreturn 1;
	return 0;
}
 
int main(){
	int i,j,h,m;
	int Case;
	scanf("%d",&Case);
	while(Case--){
		scanf("%d",&n);
		for(i=0;i
			scanf("%d:%d",&h,&m);
			t[i].ti=h*60+m;
			scanf("%d %d %d %d",&t[i].a,&t[i].b,&t[i].c,&t[i].d);
		}
 
		for(i=0;i
			for(j=0;j
				map[i][j]=pd(i,j);
		}
 
		printf("%d\n",hungary());
	}
	return 0;
}