首页 > 代码库 > HDU 1350

HDU 1350

2024-08-03 19:49:31   210人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1350

给m个顾客的乘车信息，表示几点前上车，要从一个坐标点到达另一个坐标点，花费的时间是两点的曼哈顿距离，两次换乘至少间隔1分钟（具体看样例），求最少的司机数目

把每位顾客看成一个点，如果该司机可以在接完a顾客后接到b顾客，则视为a到b连一条有向边。这个图肯定是无环的（已经接完的顾客不需要再去接），并且要用尽可能少的路径（司机）覆盖所有点，所以转化为DAG图最小路径覆盖的问题，二分图最大匹配经典模型

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <cmath>using namespace std;struct node{    int s,t,nxt ; }e[100005] ;int k,m,n,head[505],cnt,match[505],vis[505] ;int find(int s){    for(int i=head[s] ;i!=-1 ;i=e[i].nxt)    {        int tt=e[i].t ;        if(!vis[tt])        {            vis[tt]=1 ;            if(match[tt]==-1 || find(match[tt]))            {                match[tt]=s ;                return 1 ;            }        }    }    return 0 ;}int max_match(){    int ans=0 ;    memset(match,-1,sizeof(match)) ;    for(int i=1 ;i<=n ;i++)    {        memset(vis,0,sizeof(vis)) ;        ans+=find(i);    }    return ans;}void add(int s,int t) {e[cnt].s=s ;e[cnt].t=t ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;}struct point{    int x,y;};struct node1{    point s,t;    int st,ed;}kk[505];int ABS(int x){    return x>0?x:-x;}void read_graph(){    memset(head,-1,sizeof(head)) ;    cnt=0 ;    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++){            if(i==j)continue;            if(kk[i].ed+ABS(kk[i].t.x-kk[j].s.x)+ABS(kk[i].t.y-kk[j].s.y)<kk[j].st)                add(i,j);        }    }}int main(){    int T;    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=1;i<=n;i++){            int hh,mm;            scanf("%d:%d%d%d%d%d",&hh,&mm,&kk[i].s.x,&kk[i].s.y,&kk[i].t.x,&kk[i].t.y);            kk[i].st=hh*60+mm;            kk[i].ed=kk[i].st+ABS(kk[i].s.x-kk[i].t.x)+ABS(kk[i].s.y-kk[i].t.y);        }        read_graph();        printf("%d\n",n-max_match());    }    return 0;}
View Code

 

HDU 1350


联系
我们