当前位置：首页 > news >正文

poj 2060

news 来源：原创 2024/5/18 13:27:25

题意：在一个矩形城市里面，有间出租车公司收到翌日的预订行程M个，每个给出起点、终点坐标，两个地点之间的车程就是那两个点之间的曼哈顿距离，车起码要在一个行程的出发时间前一分钟到起点。求最少要多少出租车才够完成所有预订？

分析：每个起点的出发时间是确定的，起点与终点之间的距离也是确定的，因此每个行程的开始和结束的时间地点都是确定的。记A，B是两个行程的起点，A'，B'分别是终点，假如由A'到B的时间还在B的规定时间前，那么要走完AA',BB'要用的出租车就只需要一台。把起点与终于合成一个点（这样每个点就是一个行程），若A后能接上B则添加一条有向边<A,B>，把图建好之后，求出最小路径覆盖就是答案。（按照任意两个点A，B之间的时间关系，若有A到B的通路就不可能有B到A的通路，因此图中不会有环。）

PS:按照题意还是有可能存在1→2，2→3，4→2，2→5这种交叉的情况，这样就要用floyd求可达矩阵，但是加上floyd发现TLE了，于是注释掉 floyd，居然就AC了。

View Code

 1 #include<cstdio>
 2 #include<cmath>
 3 struct point
 4 {
 5     int departure,arrival;
 6     int x0,y0,x1,y1;
 7 };
 8 int mat[2][500],nx,ny;
 9 bool visited[500],matrix[500][500];
10 point p[500];
11 int path(int u)
12 {
13     int i;
14     for(i=0;i<ny;i++)
15     {
16         if(matrix[u][i] && !visited[i])
17         {
18             visited[i]=true;
19             if(mat[1][i]==-1 || path(mat[1][i]))
20             {
21                 mat[0][u]=i;
22                 mat[1][i]=u;
23                 return 1;
24             }
25         }
26     }
27     return 0;
28 }
29 int Hungary()
30 {
31     int ans=0,i,j;
32     for(i=0;i<nx;i++)
33         mat[0][i]=-1;
34     for(i=0;i<ny;i++)
35         mat[1][i]=-1;
36     for(i=0;i<nx;i++)
37     {
38         for(j=0;j<ny;j++)
39             visited[j]=false;
40         ans+=path(i);
41     }
42     return ans;
43 }
44 int format(int a,int b)
45 {
46     return a*60+b;
47 }
48 int manhattan(int x0,int y0,int x1,int y1)
49 {
50     return abs(x0-x1)+abs(y0-y1);
51 }
52 bool arrivable(int a,int b)
53 {
54     return p[a].arrival+manhattan(p[a].x1,p[a].y1,p[b].x0,p[b].y0)<p[b].departure;
55 }
56 int main()
57 {
58     int n;
59     scanf("%d",&n);
60     while(n--)
61     {
62         scanf("%d",&nx);
63         ny=nx;
64         int i,a,b,x0,y0,x1,y1;
65         for(i=0;i<nx;i++)
66         {
67             scanf("%d:%d%d%d%d%d",&a,&b,&x0,&y0,&x1,&y1);
68             p[i].departure=format(a,b);
69             p[i].arrival=p[i].departure+manhattan(x0,y0,x1,y1);
70             p[i].x0=x0;
71             p[i].y0=y0;
72             p[i].x1=x1;
73             p[i].y1=y1;
74         }
75         int j;
76         for(i=0;i<nx;i++)
77         {
78             for(j=0;j<ny;j++)
79                 matrix[i][j]=false;
80         }
81         for(i=0;i<nx;i++)
82         {
83             for(j=0;j<ny;j++)
84             {
85                 if(arrivable(i,j))
86                     matrix[i][j]=true;
87             }
88         }
89         printf("%d\n",nx-Hungary());
90     }
91     return 0;
92 }

以上代码在C++编译器下提交AC，但在GNU C++下提交就CE。提示是

1 F:\temp\11348191.4260\Main.cc: In function 'int manhattan(int, int, int, int)':
2 F:\temp\11348191.4260\Main.cc:50: error: 'abs' was not declared in this scope