概要

比赛地址

2020 Multi-University Training Contest 4

题目

1007. Go Running

题目大意

在一条双向的轴上，有若干同学在跑步，每位同学的速度是固定的 1 单位长度/s。在 n 个时刻 t，位置 x 上将至少有一个人在跑步，但是方向不确定，仅能确定有人。问能确定最少有多少同学在跑步？

分析

转化成平面图，x 轴为时间轴，y 轴为跑步的轴，则每个同学有一个起点，在一条斜率为 1 或 -1 的直线上运动。问题转化为，我们最少能用多少条斜率为 1 或 -1 的直线覆盖全部的点。

由于斜线不好处理，我们考虑将坐标轴顺时针旋转 45 度。(x,y) 的坐标被映射到 (x + y, x – y)。问题转化为在直角坐标系中，最少用多少条平行于 x 轴或者平行于 y 轴的直线覆盖全部点。

将每条平行与 x 轴的线看成二分图左边的点，平行于 y 轴的线看成二分图右边的点；原图中的每个点，就对应二分图中的一条边。问题边转化为了二分图的最小点覆盖（选取最少的点，使得每条边均有至少一个点被选中）。由相关定理，二分图的最小点覆盖等于其最大匹配。跑 Dinic 即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 50;
const int M = 1e6 + 50;
const int INF = 1e9;

int head[N], tot = 1;
struct Edge {
    int nex, to, w;
}eg[M];
void addedge(int a, int b, int c) {
    eg[++tot] = (Edge){head[a], b, c};
    head[a] = tot;
}
void add(int a, int b, int c) {
    addedge(a, b, c);
    addedge(b, a, 0);
}

struct DINIC {
    queue<int> q;
    int n, S, T;
    int dep[N], cur[N];

    void init(int _n, int _S, int _T) {
        n = _n; S = _S; T = _T;
        memset(head, 0, sizeof(head));
        tot = 1;
    }

    int bfs() {
        while(!q.empty()) q.pop();
        memset(dep, 0, sizeof(dep)); dep[S] = 1;
        q.push(S);
        while(!q.empty()) {
            int now = q.front(); q.pop();
            for(int i = head[now]; i; i = eg[i].nex) {
                int to = eg[i].to;
                if(!dep[to] && eg[i].w) {
                    dep[to] = dep[now] + 1;
                    q.push(to);
                }
            }
        }
        return dep[T] > 0;
    }
    int dfs(int rt, int flow) {
        if(rt == T || !flow) return flow;
        for(int i = cur[rt]; i; i = eg[i].nex) {
            cur[rt] = i;
            int to = eg[i].to;
            if(dep[to] == dep[rt] + 1 && eg[i].w) {
                int f = dfs(to, min(flow, eg[i].w));
                if(f) {
                    eg[i].w -= f;
                    eg[i^1].w += f;
                    return f;
                }
            }
        }
        return 0;
    }
    long long Dinic() {
        long long ans = 0;
        while(bfs()) {
            for(int i = 1; i <= n; i++) cur[i] = head[i];
            while(int tmp = dfs(S, INF)) {
                ans += tmp;
            }
        }
        return ans;
    }

}dinic;

int n;
int x[N], y[N], a[N], b[N];

int main()
{
    int ; scanf("%d", &);
    while ($--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x[i], &y[i]);
            a[i] = x[i] + y[i];
            b[i] = x[i] - y[i];
        }
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);
        int ta = (int)(unique(a + 1, a + 1 + n) - a - 1);
        int tb = (int)(unique(b + 1, b + 1 + n) - b - 1);
        int S = ta + tb + 1, T = S + 1;
        dinic.init(T, S, T);
        for (int i = 1; i <= n; i++) {
            int idx = (int)(lower_bound(a + 1, a + 1 + ta, x[i] + y[i]) - a);
            int idy = (int)(lower_bound(b + 1, b + 1 + tb, x[i] - y[i]) - b);
            add(idx, idy + ta, 1);
        }
        for (int i = 1; i <= ta; i++) {
            add(S, i, 1);
        }
        for (int i = 1; i <= tb; i++) {
            add(i + ta, T, 1);
        }
        printf("%lld\n", dinic.Dinic());
    }
    return 0;
}