HDU Go Running（最小点覆盖 + 网络流优化）

题目大意：有一条无限长跑道，每个人可以规定自己跑步的方向，起点，跑步起止时间。每个人跑步的速度都是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(){IOSint _;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,xcin >> 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