传送门

题意是说，在一个无限长的坐标轴上，给n个报点。表示在t_i时间，在x_i这个位置出现了一个人。每个人会一直往左跑或一直往右跑。起点终点均未知。

问根据给你的信息推测，最少有多少人同时在跑步。

做法是，若出现则把平面坐标上(t_i,x_i)的点染黑。由于每个人只能朝一个方向跑，那么每个点会产生一条斜率为1和斜率为-1的直线。

问题转化为选择最少的直线覆盖这n个点。

具体写的时候，把坐标绕原点旋转45度，则所有直线平行于 x轴或 y 轴，每个点(x,y)从x向y连一条边。若选择x那么表示选择了平行于x的直线，若选择y则表示选择了平行与y的直线。

问题继续转化为，对于每条边，至少要有一个点被选择。即最小点覆盖问题。也就是二分图的最大匹配。

边数比较多，大概是四倍于点，点最多是10^5，所以做的时候用网络流dinic来匹配，可以到O(n\sqrt n).

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 1e5 + 233;
unordered_map<int, int> ux, uy;
int nx[N], ny[N];
int n;
int e[N << 2], h[N << 1], pre[N << 2], f[N << 2], cnt;
void add(int u, int v)
{
    e[cnt] = v, pre[cnt] = h[u], f[cnt] = 1, h[u] = cnt++;
    e[cnt] = u, pre[cnt] = h[v], f[cnt] = 0, h[v] = cnt++;
}
int S, T;
int cntx, cnty;
int d[N << 1], cur[N << 1];

bool bfs()
{
    for(int i = 0; i <= cntx + cnty + 5; i++) d[i] = -1;
    queue<int> q;
    q.push(S), d[S] = 0, cur[S] = h[S];
    while(q.size())
    {
        int x = q.front(); q.pop();
        for(int i = h[x]; ~i; i = pre[i])
        {
            int y = e[i];
            if(d[y] == -1 && f[i])
            {
                d[y] = d[x] + 1;
                cur[y] = h[y];
                if(y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}
int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = pre[i])
    {
        cur[u] = i;
        int y = e[i];
        if(d[y] == d[u] + 1 && f[i])
        {
            int r = find(y, min(f[i], limit - flow));
            if(!r) d[y] = -1;
            f[i] -= r; f[i ^ 1] += r; flow += r;
        }
    }
    return flow;
}
int dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = find(S, 1e8)) r += flow;
    return r;
}
int main()
{
    // time_t startt = clock();

    int Tcas; 
    scanf("%d", &Tcas);
    memset(h, -1, sizeof h);
    while(Tcas--)
    {
        scanf("%d", &n);
        int tx, ty; cntx = 0, cnty = 0;
        ux.clear(); uy.clear();
        for(int i = 1; i <= n; i++) 
        {
            scanf("%d%d", &tx, &ty);
            int x = tx + ty, y = tx - ty;
            if(ux[x] == 0) ux[x] = ++cntx;
            if(uy[y] == 0) uy[y] = ++cnty;
            nx[i] = ux[x], ny[i] = uy[y];
        }

        S = 0, T = cntx + cnty + 1;
        for(int i = 0; i <= cnt; i++) h[i] = -1; cnt = 0;
        for(int i = 1; i <= n; i++) add(nx[i], ny[i] + cntx);
        for(int i = 1; i <= cntx; i++) add(S, i);
        for(int i = 1; i <= cnty; i++) add(i + cntx, T);
        printf("%d\n", dinic());
    }
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}