POJ 2060 Taxi Cab Scheme(最小パスオーバーライド)

标题:n人の乗客がタクシーで移動し、出発時間、出発場所、目的地(input保証データは出発時間の昇順に与える)を与え、少なくとも何台の車を手配して彼らの需要を満たすことができるかを聞く.
考え方:私たちは乗客一人一人の旅を一つの点と見なしています.では、i番目の人を乗せた車がi番目の人を目的地に送った後、すぐにj番目の人の出発点に出発し、j番目の人の出発時間前に駆けつけることができれば、この2人は1台の車で需要を満たすことができます.私たちは点iと点jの間に縁を作ればいいです.順番に類推して、2人の旅を列挙して、順番に判断してそれから辺を建てて、最後に最大の2点のマッチングを求めて、更に
最小パスオーバーライド=ポイント数-最大2点マッチ、
結果が得られます.

#include<cstdio>
#include<cstring>
#include<cmath>

const int N = 510;

struct point{
    int time;
    int a,b,c,d;
}p[N];

struct Edge{
    int s,e,next;
}edge[N*N];

int n,e_num,head[N],vis[N],match[N];

void AddEdge(int a,int b){
    edge[e_num].s=a; edge[e_num].e=b; edge[e_num].next=head[a]; head[a]=e_num++;
}

int dis(int i,int j){
    if(i==j)return abs(p[i].a-p[i].c)+abs(p[i].b-p[i].d);
    else return abs(p[i].c-p[j].a)+abs(p[i].d-p[j].b);
}

int dfs(int a){
    for(int k=head[a];k!=-1;k=edge[k].next){
        int i=edge[k].e;
        if(!vis[i]){
            vis[i]=1;
            if(match[i]==-1 || dfs(match[i])){
                match[i]=a;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int t,i,j,h,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d:%d%d%d%d%d",&h,&m,&p[i].a,&p[i].b,&p[i].c,&p[i].d);
            p[i].time=h*60+m;
        }
        e_num=0;
        memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++){
            for(j=i+1;j<=n;j++){
                if(p[i].time+dis(i,i)+dis(i,j)<p[j].time)
                    AddEdge(i,j);
            }
        }
        int cnt=0;
        memset(match,-1,sizeof(match));
        for(i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i)) cnt++;
        }
        printf("%d
",n-cnt);
    }
    return 0;
}