HDU 1350 Taxi Cab Scheme

题意： 老司机接客的故事 有很多顾客想要去一些地方 给你起点和终点 问最少需要多少老司机 （起点不计时

主要是坐标建图还是第一次写到 就写个题解压压惊 其实还是按照题意来就好了 再用数组链表实现邻接表存图 好像写烦了 慢了点

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
const int maxn=505;
int n,cnt;
int head[maxn],link[maxn];
bool vis[maxn];
struct point
{
    int x,y;
};
inline int dist(const point& a,const point& b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
struct edge
{
    point st,en;
    int st_time,en_time;
    void cal()
    {
        en_time=st_time+dist(st,en);
    }
} road[maxn];
struct path
{
    int st,en;
    int nxt;
}e[maxn*maxn];

void add(int u,int v)
{
    e[cnt].st=u;
    e[cnt].en=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}

void creat_gragh()
{
    memset(head,-1,sizeof head);
    cnt=0;
    for(int i=1; i<n; i++)
        for(int j=i+1; j<=n; j++)
            if(road[i].en_time+dist(road[i].en,road[j].st)<road[j].st_time) add(i,j);
}

bool dfs(int x)
{
    for(int i=head[x];i!=-1;i=e[i].nxt)
    {
        int t=e[i].en;
        if(!vis[t])
        {
            vis[t]=true;
            if(link[t]==-1||dfs(link[t]))
            {
                link[t]=x;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int num=0;
    memset(link,-1,sizeof link);
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof vis);
        if(dfs(i)) num++;
    }
    return num;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int test,hh,mm;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d:%d %d %d %d %d",&hh,&mm,&road[i].st.x,&road[i].st.y,&road[i].en.x,&road[i].en.y);
            road[i].st_time=hh*60+mm;
            road[i].cal();
        }
        creat_gragh();
        printf("%d\n",n-hungary());
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}