Beyond the Void
BYVoid
pku 2060 Taxi Cab Scheme
本文正體字版由OpenCC轉換

把每個訂單看作一個頂點,兩個訂單a,b,完成a後能在b開始之前趕到b,則向a,b連接一條有向邊。在圖中求最小路徑覆蓋即可,轉化爲二分圖最大匹配。

/* 
 * Problem: pku2060 Taxi Cab Scheme
 * Author: Guo Jiabao
 * Time: 2009.4.8 14:29
 * State: Solved
 * Memo: 最小路徑覆蓋
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=501*2*2,MAXL=201;
using namespace std;
struct quest
{
	int r,sx,sy,dx,dy;
}P[MAXN];
struct edge
{
	edge *next;
	int t;
}ES[MAXN*MAXN];
edge *V[MAXN];
bool vis[MAXN];
int N,EC=-1,Ans,Match[MAXN];
inline int cmp(const void *a,const void *b)
{
	return ((quest *)a)->r - ((quest *)b)->r;
}
inline int babs(int a){return a>0?a:-a;}
inline int dist(int x1,int y1,int x2,int y2)
{
	return babs(x1-x2)+babs(y1-y2);
}
inline bool canreach(int a,int b)
{
	int r1=dist(P[a].sx,P[a].sy,P[a].dx,P[a].dy);
	int r2=dist(P[a].dx,P[a].dy,P[b].sx,P[b].sy);
	return r1+r2<P[b].r-P[a].r;
}
inline void addedge(int a,int b)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC;V[a]->t=b;
}
void init()
{
	int i,j,h,m;
	EC=-1;
	scanf("%d",&N);
	memset(V,0,sizeof(V));
	for (i=1;i<=N;i++)
	{
		scanf("%d:%d%d%d%d%d",&h,&m,&P[i].sx,&P[i].sy,&P[i].dx,&P[i].dy);
		P[i].r=h*60+m;
	}
	qsort(P+1,N,sizeof(P[0]),cmp);
	for (i=1;i<N;i++)
	{
		for (j=i+1;j<=N;j++)
		{
			if (canreach(i,j))
				addedge(i,j+N);
		}
	}
}
bool path(int i)
{
	for (edge *k=V[i];k;k=k->next)
	{
		int j=k->t;
		if (!vis[j])
		{
			vis[j]=true;
			if (Match[j]==0 || path(Match[j]))
			{
				Match[j]=i;
				return true;
			}
		}
	}
	return false;
}
void hungary()
{
	int i,mat=0;
	memset(Match,0,sizeof(Match));
	for (i=1;i<=N;i++)
	{
		memset(vis,0,sizeof(vis));
		if (path(i))
			mat++;
	}
	Ans=N-mat;
}
int main()
{
	int i,T;
	freopen("texi.in","r",stdin);
	freopen("texi.out","w",stdout);
	scanf("%d",&T);
	for (i=1;i<=T;i++)
	{
		init();
		hungary();
		printf("%dn",Ans);
	}
	return 0;
}

上次修改時間 2017-02-03

相關日誌