週間試合POJ 2060最小パスオーバーライド
2361 ワード
标题:あなたにN人の乗客の時間をあげて、毎時間タクシーは(a,b)から(c,d)までしなければなりません.
最低どのくらいのタクシーがすべての乗客のニーズを満たすことができるかを聞く.
建図:任意の2人の乗客は、時間差を算出し、乗客1の起点から乗客2の起点までの時間を比較し、着くことができれば、つながっている.
最小パスオーバーライドを求めることです.
最低どのくらいのタクシーがすべての乗客のニーズを満たすことができるかを聞く.
建図:任意の2人の乗客は、時間差を算出し、乗客1の起点から乗客2の起点までの時間を比較し、着くことができれば、つながっている.
最小パスオーバーライドを求めることです.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define Rep(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
vector<int>g[Max] ;
bool vis[Max] ;
int link[Max] ;
void init(int n )
{
mem(vis,0) ;
mem(link,-1) ;
for (int i = 0 ; i <= n ; i ++ )g[i].clear() ;
}
int dfs(int x )
{
for (int i = 0 ; i < g[x].size() ; i ++ )
{
int e = g[x][i] ;
if(!vis[e])
{
vis[e] = 1 ;
if(link[e] == -1 || dfs(link[e]))
{
link[e] = x ;
return 1 ;
}
}
}
return 0 ;
}
struct kdq
{
int TIME ;
int a ,b , c ,d ;
}add[Max] ;
int main()
{
int T ;
cin >> T ;
while( T -- )
{
int n ;
cin >> n ;
init(n) ;
for (int i = 0 ;i < n ;i ++ )
{
int x ,y ;
scanf("%d:%d", &x, &y);
add[i].TIME = x * 60 + y ;
cin >>add[i].a >> add[i].b >> add[i].c >> add[i].d ;
}
for (int i = 0 ;i < n ;i ++ )
{
for (int j = i + 1 ; j < n ;j ++ )
{
int tt = add[j].TIME - add[i].TIME ;
int d1 = abs(add[i].a - add[i].c) + abs(add[i].b - add[i].d) ;
int d2 = abs(add[i].c - add[j].a) + abs(add[i].d - add[j].b) ;
if(d1 + d2 < tt)
g[i].push_back(j) ;
}
}
int ans = 0 ;
for (int i = 0 ; i < n ;i ++ )
{
mem(vis,0) ;
ans += dfs(i) ;
}
cout <<n - ans <<endl;
}
return 0;
}