题目大意：有一条无限长跑道，每个人可以规定自己跑步的方向，起点，跑步起止时间。每个人跑步的速度都是1m/s。最后从监控人员哪里得到了n个报告，每个报告给出了某人在某一时候所在的位置，问跑步的最少可能人数是多少。
思路：建立一个横坐标为 t ，纵坐标为 x 的二维坐标系。从输入得到的每一对 t ， x 都是坐标系上的一个点。每个人可以从东往西跑，也可以从西往东跑，所以相对应的在这个坐标系上每个点的斜率可以是 1 ，也可以是 -1 。根据这两种斜率可以得到相对应在 x 轴上的截距，然后就能够建立二分图。网络流建图就是在二分图的基础上，加上一个源点和一个汇点，然后分别建立源点和汇点到二分图的边。（网络流和二分图建图的区别是二分图两边建边的时候，可以有重复的编号，例如：1 -> 1 。但是，网络流建图的时候两个相连的点不能是重复的，例如：1 -> 2 。所以在网络流建边的时候每个编号都要保证不相同！！！）。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pii pair<int,int>
const int N=3e5+5,M=6e5+5;
struct Edge{
int to,w,next;
}edge[M];
int head[N],d[N],cur[N],l[N],r[N];
int n,m,s,t,cnt,k;
void add(int u,int v,int w){
edge[cnt]={v,w,head[u]};
head[u]=cnt++;
}
bool bfs(){
memset(d,0,sizeof d);
queue<int> q;
q.push(s);
d[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(d[v]==0 && edge[i].w){
d[v]=d[u]+1;
q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dfs(int u,int flow){
if(u==t) return flow;
int sum=0;
for(int i=cur[u];i!=-1;i=edge[i].next){
cur[u]=i;
int v=edge[i].to;
if(d[v]==d[u]+1 && edge[i].w){
int f=dfs(v,min(flow,edge[i].w));
edge[i].w-=f;
edge[i^1].w+=f;
sum+=f;
flow-=f;
if(!flow) break;
}
}
if(!sum) d[u]=0;
return sum;
}
int dinic(){
int ans=0;
while(bfs()){
memcpy(cur,head,sizeof head);
ans+=dfs(s,1e18);
}
return ans;
}
signed main(){
IOS
int _;
cin >> _;
while(_--){
cnt=0;
memset(head,-1,sizeof head);
cin >> n;
unordered_map<int,int> lx,rx;//给编号去重
int a=0,b=0;//记录两种斜率直线对于 y 轴截距的编号
for(int i=1;i<=n;i++){
int u,v;//u,v 对应 t,x
cin >> u >> v;
if(!lx.count(v-u)) lx[v-u]=++a;
if(!rx.count(v+u)) rx[v+u]=++b;
l[i]=lx[v-u],r[i]=rx[v+u];//记录每个点对应其两个截距的编号
}
for(int i=1;i<=n;i++){//二分图建边
add(l[i],r[i]+a,1);//加 a 是因为不能有重复编号
add(r[i]+a,l[i],0);
}
s=0,t=a+b+1;//添加源点和汇点
for(int i=1;i<=a;i++){//源点与二分图一边相连
add(s,i,1);
add(i,s,0);
}
for(int i=1;i<=b;i++){//汇点与二分图另一边相连
add(i+a,t,1);
add(t,i+a,0);
}
cout << dinic() << endl;//套用网络流模板
}
return 0;
}
//b=x-t lx
//b=x+t rx
