网站建设多少预算,肇庆城乡建设门户网站,郑州个人做网站汉狮,wordpress模板堂题目大意#xff1a;有一条无限长跑道#xff0c;每个人可以规定自己跑步的方向#xff0c;起点#xff0c;跑步起止时间。每个人跑步的速度都是1m/s。最后从监控人员哪里得到了n个报告#xff0c;每个报告给出了某人在某一时候所在的位置#xff0c;问跑步的最少可能人数… 题目大意有一条无限长跑道每个人可以规定自己跑步的方向起点跑步起止时间。每个人跑步的速度都是1m/s。最后从监控人员哪里得到了n个报告每个报告给出了某人在某一时候所在的位置问跑步的最少可能人数是多少。 思路建立一个横坐标为 t 纵坐标为 x 的二维坐标系。从输入得到的每一对 t x 都是坐标系上的一个点。每个人可以从东往西跑也可以从西往东跑所以相对应的在这个坐标系上每个点的斜率可以是 1 也可以是 -1 。根据这两种斜率可以得到相对应在 x 轴上的截距然后就能够建立二分图。网络流建图就是在二分图的基础上加上一个源点和一个汇点然后分别建立源点和汇点到二分图的边。网络流和二分图建图的区别是二分图两边建边的时候可以有重复的编号例如1 - 1 。但是网络流建图的时候两个相连的点不能是重复的例如1 - 2 。所以在网络流建边的时候每个编号都要保证不相同。
代码如下
#includebits/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 pairint,int
const int N3e55,M6e55;
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);queueint q;q.push(s);d[s]1;while(!q.empty()){int uq.front();q.pop();for(int ihead[u];i!-1;iedge[i].next){int vedge[i].to;if(d[v]0 edge[i].w){d[v]d[u]1;q.push(v);if(vt) return true;}}}return false;
}
int dfs(int u,int flow){if(ut) return flow;int sum0;for(int icur[u];i!-1;iedge[i].next){cur[u]i;int vedge[i].to;if(d[v]d[u]1 edge[i].w){int fdfs(v,min(flow,edge[i].w));edge[i].w-f;edge[i^1].wf;sumf;flow-f;if(!flow) break;}}if(!sum) d[u]0;return sum;
}
int dinic(){int ans0;while(bfs()){memcpy(cur,head,sizeof head);ansdfs(s,1e18);}return ans;
}
signed main(){IOSint _;cin _;while(_--){cnt0;memset(head,-1,sizeof head);cin n;unordered_mapint,int lx,rx;//给编号去重 int a0,b0;//记录两种斜率直线对于 y 轴截距的编号 for(int i1;in;i){int u,v;//u,v 对应 t,xcin u v;if(!lx.count(v-u)) lx[v-u]a;if(!rx.count(vu)) rx[vu]b;l[i]lx[v-u],r[i]rx[vu];//记录每个点对应其两个截距的编号}for(int i1;in;i){//二分图建边 add(l[i],r[i]a,1);//加 a 是因为不能有重复编号add(r[i]a,l[i],0);}s0,tab1;//添加源点和汇点for(int i1;ia;i){//源点与二分图一边相连 add(s,i,1);add(i,s,0);}for(int i1;ib;i){//汇点与二分图另一边相连 add(ia,t,1);add(t,ia,0);}cout dinic() endl;//套用网络流模板 }return 0;
}
//bx-t lx
//bxt rx
