OI - Go Running(HDU) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Go Running(HDU)

发表于 分类于 Valine：

今年的八月来得格外的早……

# 题面

> Linked HDU 6808

点击展开/折叠题面

有若干个人在数轴上跑步，具体来说，一个人会从某一个时刻（秒）开始，从某一个位置（整数点）出发，向正方向或反方向以 $1$ 单位长度每秒的速度跑步。

你限制知道 $n$ 个信息，第 $i$ 个信息形如“$x_i,t_i$”表示 $t_i$ 时刻（秒），$x_i$ 位置（整数点）有至少一个人。

求最少有多少个人在跑步。

# 解析

因为一个人跑步的速度是恒定的，如果我们画出他的 $v$-$t$ 图像，一定是一条直线，斜率为 $1$ 或 $-1$。

给出的 $(x_i,t_i)$ 可以绘制在直角坐标系的 $n$ 个整点上，如果一个人的 $v$-$t$ 图像经过了某个点，则这个点代表的信息就成立了。

于是我们发现问题变为这样：给出平面直角坐标系中的 $n$ 个点，求用斜率为 $1$ 或 $-1$ 的直线覆盖这些点最少需要多少条。其实仍然不是很方便，把图像整个旋转 $45^\circ$，就变成用水平、竖直的直线来覆盖这些点了。

那么对于一个点 $(x_0,y_0)$，只要存在 $x=x_0$ 或 $y=y_0$ 这两条直线中的一条，就满足条件了。

于是把条件建出二分图：X部表示横坐标 $x_i$，Y部表示纵坐标 $y_i$，对于点 $(x_0,y_0)$ 在 $x_0,y_0$ 之间连边。

则现在要做的就是选择 X,Y部 的一些点，覆盖每一条边，即最小点覆盖问题。经典的结论就是二分图最小点覆盖=最大匹配，所以用 Dinic 跑一跑就好了。

# 源代码

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
87
88
89
90
91
92
93
94
95
96
97
98
99
/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10,INF=1e9;

inline int Ri(){
    register int r=0,c=getchar();
    while(c<'0' || '9'<c) c=getchar();
    while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
    return r;
}

int n,S,T;
int x[N],y[N],dis[N<<1],head[N<<1];
vector<int> unix,uniy;

struct GRAPH{
    int head[N<<1],nxt[N*6],to[N*6],cap[N*6],ncnt;
    void Init(int siz){
        for(int i=0;i<=siz;i++) head[i]=0;
        ncnt=1;
    }
    void AddEdge(int u,int v,int ca){
//        printf("%d ->(%d)-> %d\n",u,ca,v);
        int p=++ncnt,q=++ncnt;
        nxt[p]=head[u],to[p]=v,cap[p]=ca,head[u]=p;
        nxt[q]=head[v],to[q]=u,cap[q]=0 ,head[v]=q;
    }
    int operator [](const int &u){return head[u];}
}Gr;

bool BFS(){
    for(int i=1;i<=T;i++) dis[i]=-1,head[i]=Gr[i];
    queue<int> que;
    que.push(S),dis[S]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int it=head[u];it;it=Gr.nxt[it]){
            int v=Gr.to[it];
            if((~dis[v]) || Gr.cap[it]<=0) continue;
            dis[v]=dis[u]+1;
            if(v==T) return true;
            que.push(v);
        }
    }
    return false;
}
int Aug(int u,int in){
//    printf("? %d %d\n",u,in);
    if(u==T) return in;
    int out=0;
    for(int &it=head[u];it;it=Gr.nxt[it]){
        int v=Gr.to[it];
        if(Gr.cap[it]<=0 || dis[v]!=dis[u]+1) continue;
        int tov=Aug(v,min(in-out,Gr.cap[it]));
        out+=tov;
        Gr.cap[it]-=tov,Gr.cap[it^1]+=tov;
        if(out==in) break;
    }
    return out;
}
int Dinic(){
    int ret=0;
    while(BFS())
        ret+=Aug(S,INF);
    return ret;
}

int main(){
    for(int cas=Ri();cas;cas--){
        n=Ri();
        unix.clear(),uniy.clear();
        for(int i=1;i<=n;i++){
            int a=Ri(),b=Ri();
            x[i]=a+b,y[i]=a-b;
            unix.push_back(x[i]);
            uniy.push_back(y[i]);
        }
        sort(unix.begin(),unix.end()),unix.erase(unique(unix.begin(),unix.end()),unix.end());;
        sort(uniy.begin(),uniy.end()),uniy.erase(unique(uniy.begin(),uniy.end()),uniy.end());;
        int p=unix.size(),q=uniy.size();
        S=p+q+1,T=S+1;
        Gr.Init(T);
        for(int i=1;i<=p;i++) Gr.AddEdge(S,i,1);
        for(int i=p+1;i<S;i++) Gr.AddEdge(i,T,1);
        for(int i=1;i<=n;i++){
            x[i]=lower_bound(unix.begin(),unix.end(),x[i])-unix.begin()+1,
            y[i]=lower_bound(uniy.begin(),uniy.end(),y[i])-uniy.begin()+1;
            Gr.AddEdge(x[i],y[i]+p,1);
        }
        printf("%d\n",Dinic());
    }
    return 0;
}

THE END

Thanks for reading!

> Linked 琉璃-网易云