网站建设 移动端,快递网站建站需要什么,国土资源局网站建设制度,有了网站 怎么做排名优化1 /*2 题意#xff1a; 出租车 有一个出发的时间#xff0c;从点#xff08;a, b#xff09;到点#xff08;c, d#xff09;#xff0c;时间为3 abs(a-c)abs(b-d)! 一辆车可以在运完一个乘客后运另一个乘客, 4 条件是此车要在预约开始前一分钟之前到达出发地,… 1 /*2 题意 出租车 有一个出发的时间从点a, b到点c, d时间为3 abs(a-c)abs(b-d)! 一辆车可以在运完一个乘客后运另一个乘客, 4 条件是此车要在预约开始前一分钟之前到达出发地, 问最少需要几辆车5 搞定所有预约。6 7 思路有向边进行建图因为出发时间是升序的8 t0: (a0, b0) -(c0, d0)表示预约在t0时间出发从(a,b)到(c,d);//节点x 9 t1: (a1, b1) -(c1, d1)表示预约在t1时间出发从(a1,b1)到(c1,d1);//节点y
10
11 如果可能的话从t0时间出发的车到达目的地后如果满足从c,d)到a1,b1)
12 也就是从第一个目的地到达下一个出发地的时间t2 1t1, 那么完全就不用
13 其他的车再来了两次的预约都搞定了
14 如果满足的话节点x 和 节点y建立一条有向边
15 最后通过匈牙利算法搞定.....
16 */
17 #includeiostream
18 #includecmath
19 #includecstdio
20 #includecstring
21 #includealgorithm
22 #includevector
23 #define M 505
24 using namespace std;
25
26 struct point{
27 int x, y;
28 point(){}
29 point(int x, int y){
30 this-xx;
31 this-yy;
32 }
33 int operator -(point a) {
34 return abs(x-a.x) abs(y-a.y);
35 }
36 };
37
38 struct node{
39
40 int begin, end;
41 point s, d;
42 };
43
44 node nd[M];
45 vectorintv[M];
46 int vis[M];
47 int link[M];
48
49 int n;
50
51 bool dfs(int cur){
52 int lenv[cur].size();
53 for(int i0; ilen; i){
54 int uv[cur][i];
55 if(vis[u]) continue;
56 vis[u]1;
57 if(!link[u] || dfs(link[u])){
58 link[u]cur;
59 return true;
60 }
61 }
62 return false;
63 }
64
65 int main(){
66 int t;
67 scanf(%d, t);
68 while(t--){
69
70 scanf(%d, n);
71 for(int i1; in; i){
72 int b, e, x1, y1, x2, y2;
73 scanf(%d:%d %d %d %d %d, b, e, x1, y1, x2, y2);
74 nd[i].beginb*60e;
75 nd[i].spoint(x1, y1);
76 nd[i].dpoint(x2, y2);
77 nd[i].endnd[i].begin(nd[i].s-nd[i].d);
78 }
79 for(int i1; in; i)
80 for(int ji1; jn; j){
81 if(nd[j].beginnd[i].end(nd[i].d-nd[j].s)1)//如果能够满足条件爱你到达另一个出发地点两个节点之间建立一条有向边
82 v[i].push_back(j);
83 }
84 int ans0;
85 memset(link, 0, sizeof(link));
86 for(int i1; in; i){
87 memset(vis, 0, sizeof(vis));
88 if(dfs(i)) ans;
89 }
90 coutn-ansendl;
91 for(int i1; in; i)
92 v[i].clear();
93 }
94 return 0;
95 } 转载于:https://www.cnblogs.com/hujunzheng/p/3917850.html
