hdu 1350+hdu 1960(最小路径覆盖）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1350

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

思路：最小路径覆盖，即如果两条路线的时间不冲突，那么就连边，最后求一下最大匹配就可以了。

最小路径覆盖=顶点数-最大匹配。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 #define MAXN 2222
 9 vector<int>map[MAXN];
10 struct Point{
11    int x,y;
12 };
13 struct Node{
14    int st,ed;
15    Point p1,p2;
16 }node[MAXN];
17 bool mark[MAXN];
18 int lx[MAXN],ly[MAXN];
19 int n;
20 
21 int Get_Time(const Point &p1,const Point &p2){
22    int d1=abs(p1.x-p2.x);
23    int d2=abs(p1.y-p2.y);
24    return d1+d2;
25 }
26 
27 int dfs(int u){
28    for(int i=0;i<map[u].size();i++){
29       int v=map[u][i];
30       if(!mark[v]){
31          mark[v]=true;
32          if(ly[v]==-1||dfs(ly[v])){
33             ly[v]=u;
34             lx[u]=v;
35             return 1;
36          }
37       }
38    }
39    return 0;
40 }
41 
42 int MaxMatch(){
43    int res=0;
44    memset(lx,-1,sizeof(lx));
45    memset(ly,-1,sizeof(ly));
46    for(int i=1;i<=n;i++){
47       if(lx[i]==-1){
48          memset(mark,false,sizeof(mark));
49          res+=dfs(i);
50       }
51    }
52    return res;
53 }
54 
55 int main(){
56 //   freopen("1.txt","r",stdin);
57    int _case,h,m;
58    scanf("%d",&_case);
59    while(_case--){
60       scanf("%d",&n);
61       for(int i=1;i<=n;i++)map[i].clear();
62       for(int i=1;i<=n;i++){
63          scanf("%d:%d %d %d %d %d",&h,&m,&node[i].p1.x,&node[i].p1.y,&node[i].p2.x,&node[i].p2.y);
64          node[i].st=h*60+m;
65          node[i].ed=node[i].st+Get_Time(node[i].p1,node[i].p2);
66       }
67       for(int i=1;i<=n;i++){
68          for(int j=i+1;j<=n;j++){
69             if(node[i].ed+Get_Time(node[i].p2,node[j].p1)<node[j].st){
70                map[i].push_back(j);
71             }
72          }
73       }
74       int ans=MaxMatch();
75       printf("%d\n",n-ans);
76    }
77    return 0;
78 }

View Code