poj2060

发表于 | 分类于

有n个任务，给出任务时间和起点终点，每两个点之间的时间花费为其曼哈顿距离，问若要每个任务都按时开始需要多少出租车。

并不是很难，就是题意理解起来可能会有些问题，反正我当时是WA了几遍之后才发现的，a到b能连边，需满足a的开始时间+到终点花费+从a的终点到b的起点的花费<=b的开始时间
将图建好之后就简单了，直接跑一遍匈牙利求最小路径覆盖=总点数-最大匹配即可。

还get到了一个scanf的新用法：scanf("%d:%d",&a,&b)可以直接跳过去中间的’:’直接读入b，当时用的getchar还RE了几遍，用这个就AC了QAQ

附上题目链接：poj2060

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int tot;
int had[1030],point[500*500+2],nxt[500*500+2];
int fa[1004];
bool vis[1003];
inline void add(int x,int y)
{
    tot++;
    point[tot]=y;
    nxt[tot]=had[x];
    had[x]=tot;
}
bool cando(int x)
{
    for(int i=had[x];i;i=nxt[i])
    {
        int to=point[i];
        if(!vis[to])
        {
            vis[to]=1;
            if(fa[to]==0||cando(fa[to]))
            {
                fa[to]=x;
                return 1;
            }
        }
    }
    return 0;
}
int n,m,t;
struct dou{
    int stt,nd;
    int s1,s2,e1,e2;
}p[504];
inline int ab(int x)
{
    if(x<0)return -x;
    return x;
}
inline bool line(int x,int y)
{
    int dis=ab(p[x].e1-p[y].s1)+ab(p[x].e2-p[y].s2);
    if(p[x].nd+dis<p[y].stt)return 1;
    return 0;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        tot=0;
        int day=0;
        memset(fa,0,sizeof(fa));
        memset(had,0,sizeof(had));
        int a,b;
        for(int i=1;i<=n;i++)
        {
            scanf("%d:%d",&a,&b);
            p[i].stt=a*60+b;
            scanf("%d%d%d%d",&p[i].s1,&p[i].s2,&p[i].e1,&p[i].e2);
            p[i].nd=p[i].stt+ab(p[i].s1-p[i].e1)+ab(p[i].s2-p[i].e2);
            while(p[i].stt<p[i-1].stt)
            {
                p[i].stt+=24*60;
                p[i].nd+=24*60;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                if(line(i,j))add(i,j+n);
    //	for(int i=1;i<=n;i++)
    //		cout<<p[i].stt<<' '<<p[i].nd<<endl;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(cando(i))ans++;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}