2060 Taxi Cab Scheme

問題概要

タクシーのスケジュールが"時間 タクシーの出発位置 目的地"のリストにより与えられる。
このとき、スケジュールを満たすために必要なタクシーの最小の台数を求めよ。

タクシーの台数は500以下、
任意の二点(x,y) (v,w)をタクシーが移動するのにかかる時間は|x-v|+|y-w|分、
客を乗せたタクシーが次の客を乗せるためには、次の客の出発位置に1分以上前につかなければならないものとする。

解法

先日の模擬地区予選のMerry Christmasとほぼ同じ問題。
客Aを乗せたタクシーが次に客Bを運べるとき、A→Bに辺を張るものとすると、DAGができる。
DAGの最小パス被覆は、頂点を二倍にした二部グラフのマッチングにより解ける。

ソースコード

int n,m,sx[500],sy[500],dx[500],dy[500];
int t[500],move[500],p[1000];
char in[9]; vector<vi> e; bool v[1000];

bool match(int s)
{
	if(s<0)return 1;
	fr(i,e[s])if(!v[*i])
	{
		v[*i]=1;
		if(match(p[*i]))return p[s]=*i,p[*i]=s,1;
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	rep(it,n)
	{
		scanf("%d",&m);
		rep(i,m)
		{
			scanf("%s%d%d%d%d",in,sx+i,sy+i,dx+i,dy+i);
			t[i]=(in[0]-'0')*600+(in[1]-'0')*60+(in[3]-'0')*10+in[4]-'0';
			move[i]=abs(sx[i]-dx[i])+abs(sy[i]-dy[i]);
		}
		e.clear(); e.resize(2*m);
		rep(j,m)rep(i,j)if(t[j]>t[i]+move[i]+abs(dx[i]-sx[j])+abs(dy[i]-sy[j]))
		e[i].pb(m+j),e[m+j].pb(i);
		
		int ans=m;
		rep(i,2*m)p[i]=-1;
		rep(i,m)
		{
			rep(j,2*m)v[j]=0;
			if(match(i))ans--;
		}
		printf("%d\n",ans);
	}
	return 0;
}