## 【二分图匹配】Go Running – HDU20多校4G

### 传送门

#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;
}