2020HDU多校第四场 Go Running

题意：同学们在操场跑步(操场看做无限长的数轴),每个同学如果开始跑步那么他跑步的方向不会改变直到时间结束。老师为了检查是否有同学偷懒没有跑步，手上有 份监测报告，每份监测报告说明了在 时刻时， 位置至少有一个人在跑步。问操场上至少有多少名学生没有偷懒在跑步。

分析：将每个时刻的(t,pos) 看作二维平面上的点，那么对应的同学看作斜率为45°,135°的两条直线。将所有点旋转45°，那么所有的直线就是垂直于坐标轴，那么该问题转换成了选取最少的直线覆盖所有点。将第 个点产生的垂直于轴的直线和垂直于 轴的直线，看成点，并且连一条边，建二分图，那么问题转换成了二分图的最小点覆盖问题，而二分图的最小点覆盖等于二分图的最大匹配。
由于n的范围比较大，选择比较高效的二分匹配算法Donic. .

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5;

namespace flow {

    struct edge {
        int to, cap, flow, rev;
    };
    vector<edge> g[maxn + 10];
    int s, t, ndcnt, d[maxn + 10], cur[maxn + 10];
    queue<int> q;

    void init(int ss, int tt, int nn) {
        s = ss; t = tt;
        for (int i = 1; i <= ndcnt; ++i) g[i].clear();
        ndcnt = nn;
    }

    void add(int l, int r, int w) {
        g[l].push_back((edge){r, w, 0, (int)g[r].size()});
        g[r].push_back((edge){l, 0, 0, (int)g[l].size() - 1});
    }

    bool bfs() {
        for (int i = 1; i <= ndcnt; ++i)
            d[i] = i == s ? 0 : -1;
        q.push(s);
        while (!q.empty()) {
            int p = q.front(); q.pop();
            for (int i = 0; i < (int)g[p].size(); ++i) {
                edge e = g[p][i];
                if (e.cap > e.flow && d[e.to] == -1) {
                    d[e.to] = d[p] + 1; q.push(e.to);
                }
            }
        }
        return d[t] != -1;
    }

    int dfs(int p, int a) {
        if (p == t) return a;
        int ans = 0, now;
        for (int &i = cur[p]; i < (int)g[p].size(); ++i) {
            edge &e = g[p][i];
            if (e.cap > e.flow && d[p] + 1 == d[e.to]) {
                now = dfs(e.to, min(a, e.cap - e.flow));
                e.flow += now; g[e.to][e.rev].flow -= now;
                ans += now; a -= now; if (!a) break;
            }
        }
        return ans;
    }

    int solve() {
        int ans = 0;
        while (bfs()) {
            for (int i = 1; i <= ndcnt; ++i) cur[i] = 0;
            ans += dfs(s, 1e9);
        }
        return ans;
    }

}

int n, x[maxn + 10], y[maxn + 10];
int l[maxn + 10], r[maxn + 10], sl, sr;

int main() {
    int T; 
    scanf("%d", &T); 
    while ( T-- ) 
    {
        int n; 
        scanf("%d", &n);


        for ( int i = 1; i <= n; ++i ) 
        {
            int a, b; 
            scanf("%d%d", &a, &b);
            x[i] = a + b; y[i] = a - b;
        }

        sl = sr = 0;

        for ( int i = 1; i <= n; ++i ) 
        {
            l[++sl] = x[i]; r[++sr] = y[i];
        }

        sort(l + 1, l + sl + 1);
        sl = unique(l + 1, l + sl + 1) - l - 1;

        sort(r + 1, r + sr + 1);
        sr = unique(r + 1, r + sr + 1) - r - 1;

        flow::init(1, 2, 2 + sl + sr);

        for (int i = 1; i <= sl; ++i) flow::add(1, i + 2, 1);

        for (int i = 1; i <= sr; ++i) flow::add(i + sl + 2, 2, 1);


        for ( int i = 1; i <= n; ++i ) 
        {
            x[i] = lower_bound(l + 1, l + sl + 1, x[i]) - l;
            y[i] = lower_bound(r + 1, r + sr + 1, y[i]) - r;
            flow::add(x[i] + 2, y[i] + sl + 2, 1);
        }

        printf("%d\n", flow::solve());

    }

}