POJ-2060-Taxi Cab Scheme

POJ-2060-Taxi Cab Scheme
http://poj.org/problem?id=2060
예약 의 시작 시간,출발지 와 목적 지 를 제시 하고 적어도 몇 대의 차 가 필요 하 냐 고 물 으 면 모든 예약 을 만족 시 킬 수 있 습 니 다.
한 쌍 의 예약 에 대해 만약 에 앞의 예약 의 끝 시간 에 다음 예약 에 도착 하 는 데 소요 되 는 시간 이 다음 예약 의 시작 시간 보다 적 으 면 두 예약 사이 에 한 변 을 연결 하고 제목 은 이 그림 의 가장 작은 길 을 찾 는 것 으로 바 뀌 었 다.
가장 작은 길 은 힘 으로 덮는다.
전환 하 다 http://baike.baidu.com/view/2444809.htm
하나의 PXP 의 방향 그림 에서 경 로 를 덮어 쓰 는 것 은 그림 에서 경 로 를 찾 아 그림 의 모든 정점 을 덮어 쓰 고 그 어떠한 정점 도 있 으 며 하나의 경로 만 이 관련 되 어 있 습 니 다.(이 경로 의 모든 경 로 를 시작 점 에서 종점 까지 걸 어가 면 마침 그림 의 모든 정점 을 한 번,한 번 만 지나 갈 수 있 습 니 다).그림 에 회로 가 존재 하 는 것 을 고려 하지 않 으 면 모든 경 로 는 약 한 연결 부분 집합 이다.
위 에서 얻 을 수 있다.
1.하나의 단독 정점 은 하나의 경로 이다.
2.만약 에 경로 p1,p2,...pk 가 존재 한다 면 그 중에서 p1 을 기점 으로 하고 pk 를 종점 으로 한다 면 덮어 쓰기 그림 에서 정점 p1,p2,...pk 는 다른 정점 과 방향 이 존재 하지 않 습 니 다.
최소 경 로 를 덮어 쓰 는 것 은 최소 경 로 를 찾 아 P 의 경로 로 덮어 쓰 는 것 입 니 다.
경로 덮어 쓰기 2 분 그림 과 일치 하 는 관계(원 이 없 는 방향 그림 이 어야 합 니 다):
최소 경로 덮어 쓰기=|P|-그 중에서 가장 큰 일치 수의 구법 은 P 의 모든 정점 pi 를 두 개의 정점 pi'와 pj'로 나 누 는 것 입 니 다.p 에 pi 가 pj 의 변 에 존재 한다 면 2 분 그림 P'에 pi'와 pj'를 연결 하 는 무 방향 변 이 있 습 니 다.여기 pi'는 p 중 pi 의 아웃 사 이 드 이 고 pj'는 p 중 pj 의 입 사 이 드 입 니 다.
공식:최소 경로 덮어 쓰기=|P|-최대 일치 수;이렇게 이해 할 수 있다.
일치 수가 0 이면 P 에 방향 이 없 기 때문에 다음 과 같 습 니 다.
최소 경로 덮어 쓰기=|P|-최대 일치 수=|P|-0=|P|;즉,P 의 최소 경로 덮어 쓰기 수 는|P|입 니 다.
P'에서 일치 하 는 쪽 이 아 닐 때 경로 덮어 쓰기 수 는|P|입 니 다.
P'에 일치 하 는 변 pi'－>pj'를 추가 하면 그림 P 의 경로 커버 에 pi 로 pj 를 연결 하 는 변 이 존재 합 니 다.즉,pi 와 pj 가 한 경로 에 있 기 때문에 경로 커버 수 는 하 나 를 줄 일 수 있 습 니 다.
이렇게 해서 일치 하 는 쪽 을 계속 늘 리 고 하 나 를 늘 릴 때마다 경로 덮어 쓰기 수가 줄 어 듭 니 다.일치 하 는 변 이 계속 증가 하지 않 을 때 까지 경로 커버 수 를 더 이상 줄 일 수 없습니다.이때 앞의 공식 이 있 습 니 다.그러나 여 기 는 모든 일치 변 이 경로 덮어 쓰기 에 대응 하 는 경로 의 한 연결 두 점 사이 의 방향 변 을 설명 할 뿐이다.다음은 하나의 경로 가 겹 쳐 진 모든 연결 두 정점 사이 의 방향 변 이 일치 하 는 변 에 대응 하 는 것 을 설명 한다.
앞 과 유사 합 니 다.경로 덮어 쓰기 에 있 는 모든 연결 두 정점 사이 의 모든 방향 pi->pj 가 있 습 니 다.우 리 는 일치 하 는 그림 에서 pi'와 pj'를 연결 하 는 변 을 만 들 수 있 습 니 다.분명히 이렇게 그림 을 만 든 것 은 일치 하 는 그림 입 니 다.(이 점 은 반증 법 으로 쉽게 증명 할 수 있 습 니 다.만약 에 얻 은 그림 이 일치 하 는 그림 이 아니라면...그러면 이 그림 에는 반드시 이런 두 개의 변 pi'-pj'와 pi'-pk'가 존재 합 니 다.(j!=k)그러면 경로 덮어 쓰기 그림 에 두 개의 변 pi->pj,pi->pk 가 존재 합 니 다.저쪽 에 pi 에서 출발 하 는 경 로 는 한 가지 가 아 닙 니 다.이것 은 경로 덮어 쓰기 그림 과 모순 되 는 것 입 니 다.또 다른 상황 은 pi'-pj',pk'-pj'가 존재 하 는데 이런 상황 도 증명 할 수 있 는 것 과 유사 하 다.
이로써 일치 변 과 경로 덮어 쓰기 그림 에서 두 정점 사 이 를 연결 하 는 일일이 대응 하 는 관 계 를 설명 한다.그러면 앞의 공식 이 성립 되 었 음 을 설명 한다!

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 600
struct node
{
	int st,ed;
	int a,b,c,d;
}list[N*6];
int map[N][N];
int result[N];
int visit[N];
int n;
int cmp(const void *a,const void *b)
{
	return (*(struct node *)a).st-(*(struct node *)b).st;
}
int find(int a)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(!visit[i]&&map[a][i])
		{
			visit[i]=1;
			if(!result[i]||find(result[i]))
			{
				result[i]=a;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int t,i,j,temp;
	int hour,minute,ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d:%d %d %d %d %d",&hour,&minute,&list[i].a,&list[i].b,&list[i].c,&list[i].d);
			list[i].st=hour*60+minute;
			list[i].ed=list[i].st+abs(list[i].a-list[i].c)+abs(list[i].b-list[i].d);
		}
		qsort(list+1,n,sizeof(list[0]),cmp);
		memset(map,0,sizeof(map));
		for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
		{
			temp=abs(list[i].c-list[j].a)+abs(list[i].d-list[j].b);
			if(list[i].ed+temp<list[j].st)
			map[i][j]=1;
		}
		ans=0;
		memset(result,0,sizeof(result));
		for(i=1;i<=n;i++)
		{
			memset(visit,0,sizeof(visit));
			if(find(i))
			ans++;
		}
		printf("%d
",n-ans);
	}
	system("pause");
	return 0;
}