本文共 1348 字，大约阅读时间需要 4 分钟。

一个人如果在 $(a,b)$ 点到 $(c,d)$

乘出租车需要花费的时间为$|c-a|+|d-b|$

如果一辆车可以在乘客出发前的达到（不取等），就可以接到该乘客。

现在收到了 n 份订单，求最少用多少出租车，可以完成所有的任务。

#include 
   
    using namespace std;const int maxn = 2e5+10;int n,m,a[maxn],b[maxn],c[maxn],D[maxn];struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt] = (edge){
   v,head[u]},head[u] = cnt;}int match[maxn],used[maxn],tim[maxn];bool find(int x){
   	for(int i=head[x];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( used[v] )	continue;		used[v] = 1;		if( match[v]==0||find( match[v]) )		{
   			match[v] = x;			return true;		}	}	return false;}int isok(string s){
   	return (s[0]-'0')*10*60+(s[1]-'0')*60+(s[3]-'0')*10+(s[4]-'0');}int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n;		for(int i=1;i<=n;i++)		{
   			string s;			cin >> s >> a[i] >> b[i] >> c[i] >> D[i];			tim[i] = isok(s);		}		for(int i=1;i<=n;i++)		{
   			int w = abs( a[i]-c[i] )+abs( b[i]-D[i] );			for(int j=1;j<=n;j++)			{
   				int ww = w+abs( c[i]-a[j] )+abs( D[i]-b[j] );				if( tim[j]-tim[i]-1>=ww )//可以从i到j					add(i,j+n); 			}		}		int ans = 0;		for(int i=1;i<=n;i++)		{
   			memset( used,0,sizeof(used) );			if( find(i) )	ans++;		}		cout << n-ans << endl;		cnt = 1;		for(int i=1;i<=2*n;i++)	head[i] = 0;		memset( match,0,sizeof(match) );	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110005119 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！