Practice link: https://vjudge.net/problem/HDU-6808
题意：给你有 x 和 t 组成的点，表示某个人在 t 时刻位置为 x，问你至少有几个人。
思路：因为每个人可以跑的方向不确定，因此一个点可以得到两条直线，那么题意就变成了最少需要几条直线可以覆盖所有点。我们可以用 点（x，t)看出边，即 x+t 和 x-t两条边都有可能是经过这个点的人，那么我们可以开始建图了，即用一个点看出两条线 x+t 和 x-t ，再将这两条线连接，即表示选取其中一条线就可以覆盖这个点，那么问题就转化为了在二分图中的最小点覆盖问题，最小点覆盖 = 二分图最大匹配，用匈牙利算法跑一遍即可。但是需要注意的是 两条直线需要需要进行重新标号，即对于所有的 x+t （首次出现）标号为 从1开始，对于 x-t（首次出现）也从一开始，建边时只需要建立单向边即可。
代码：
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define INF 0x3f3f3f3f 4 #define mem(a,x) memset(a,x,sizeof(a)) 5 #define _for(i,a,b) for(int i=a; i< b; i++) 6 #define _rep(i,a,b) for(int i=a; i<=b; i++) 7 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 8 using namespace std; 9 const int NUM = 100005 ; 10 int n; 11 int a[NUM],b[NUM]; 12 int link[NUM]; 13 bool vis[NUM]; 14 vector<int>g[4*NUM]; 15 map<int,int>m1,m2; 16 bool dfs(int x) 17 { 18 for(int i=0;i<g[x].size();i++){ 19 int v=g[x][i]; 20 if(!vis[v]){ 21 vis[v]=1; 22 if(!link[v]||dfs(link[v])){ 23 link[v]=x; 24 return true; 25 } 26 } 27 } 28 return false; 29 } 30 int main() 31 { 32 int T; 33 scanf("%d",&T); 34 while(T--){ 35 m1.clear(); 36 m2.clear(); 37 scanf("%d",&n); 38 for(int i=1;i<=n;i++){ 39 g[i].clear(); 40 } 41 int u=0,vv=0; 42 for(int i=1;i<=n;i++){ 43 int t,x; 44 scanf("%d %d",&t,&x); 45 a[i]=x-t; 46 b[i]=x+t; 47 if(!m1[a[i]]){ 48 m1[a[i]]=++u; 49 } 50 if(!m2[b[i]]){ 51 m2[b[i]]=++vv; 52 } 53 54 g[m1[a[i]]].push_back(m2[b[i]]); 55 link[i]=0; 56 vis[i]=0; 57 } 58 int ans=0; 59 for(int i=1;i<=u;i++){ 60 mem(vis,0); 61 if(dfs(i))ans++; 62 } 63 cout<<ans<<endl; 64 } 65 return 0; 66 }