大意：在一个二维坐标系上有nx个人和ny把伞，每个人都有自己的移动速度，问有多少人可以再 time 时间内移动到不同的雨伞处（不允许两个人共用一把伞）。
输入数据：
第一行是一个T代表T组测试数据。
开始是一个数字 time (1 <=time<= 5) 代表还有t时间就开始下雨了。
接下来是一个数字m代表宾客的数量。
接下来m行每行一个x,y 代表宾客所在的坐标， s代表宾客移动的速度
然后是一个数字n 代表伞的数量。
接下来n行就是伞的坐标。（所有坐标的绝对值是小于10000的）
输出：
在规定时间内最多有多少人可以拿到伞
题目解析：
以人和伞建立二分图，如果人能在规定时间内到达 这个伞，那么我们就以人和伞之间建边。
事实上经过验证超时了，那么换种方法，经过百度发现是需要一个Hopcroft-Carp（也有叫Hopcroft-Karp反正也是傻傻分不清楚）
这道题目要是使用vetor建立邻接表也是会超时的 毕竟数据量比较大
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> #include<queue> #include<cmath> using namespace std; #define INF 0x3fffffff #define maxn 3005 bool vis[maxn]; int Px[maxn], Py[maxn];///Px[i]表示在X集合的i 所匹配Y的值的编号是 P[i] int dx[maxn], dy[maxn], Head[maxn];///dx记录X集合每个点所在的层， dy同dx int n, m, depth, k; struct node { int x, y, s;///这个点的坐标集，人移动的速度 }Peo[maxn], Umb[maxn];///分别表示人的坐标点集， 和伞所在位置的点集 struct Edge { int v, next; }e[maxn*maxn]; void Add(int a,int b) { e[k].v = b; e[k].next = Head[a]; Head[a] = k; k ++; } void Init() { k = 0; memset(e, 0, sizeof(e)); memset(Px, -1, sizeof(Px)); memset(Py, -1, sizeof(Py)); memset(Head, -1, sizeof(Head)); } bool BFS() { queue<int> Q; depth = INF;///记录深度 memset(dx, -1, sizeof(dx)); memset(dy, -1, sizeof(dy)); for(int i=0; i<n; i++) { if(Px[i] == -1) {///以x方的点为源点，进行广搜, 并且是没有加入匹配的点 Q.push(i); dx[i] = 0; } } while( Q.size() ) { int u = Q.front(); Q.pop(); if(dx[u] > depth)///????? break; for(int i=Head[u]; i != -1; i = e[i].next) { int v = e[i].v; if(dy[v] == -1) { dy[v] = dx[v] + 1; /**说明这个点是没有加入到匹配内的， 也就是说我们找到了一条增广路 (因为我们的源点是没进入匹配内的点，而源点到达的这个点也是没有进入匹配的点， 两个未进入匹配的点，相连了肯定是一对匹配，也就是增广路)*/ if(Py[v] == -1) depth = dy[v]; else///否则源点所连接的就是匹配过的点。 { dx[Py[v]] = dy[v] + 1; Q.push( Py[v] ); } } } } return depth != INF; } bool Find(int u) { for(int i=Head[u]; i != -1; i = e[i].next) { int v = e[i].v; if(!vis[v] && dx[u] == dy[v] - 1)///由dx[i]到 dy[v] 可以寻得一条增广路 { vis[v] = true; /**增广路不在这里，因为我们在dy[v]这个深度的时候已经找到增广路了*/ if(Py[v] != -1 && dy[v] == depth) continue; if(Py[v] == -1 || Find(Py[v])) { Py[v] = u; Px[u] = v; return true; } } } return false; } int solve() { int ans = 0; while( BFS() )///确定是否存在增广路 { memset(vis, false, sizeof(vis)); for(int i=0; i<n; i++) { if(Px[i] == -1 && Find(i) ) ans ++; } } return ans; } int main() { int T, time, cas = 1;///n 人的个数 m伞的个数 scanf("%d", &T); while(T--) { scanf("%d %d", &time, &n); for(int i=0; i<n; i++) scanf("%d %d %d",&Peo[i].x, &Peo[i].y, &Peo[i].s); scanf("%d", &m); for(int i=0; i<m; i++) scanf("%d %d", &Umb[i].x, &Umb[i].y); Init(); for(int i=0; i<n; i++)///构图 { for(int j=0; j<m; j++) { double len = sqrt( 1.0*(Peo[i].x-Umb[j].x)*(Peo[i].x-Umb[j].x) + (Peo[i].y-Umb[j].y)*(Peo[i].y-Umb[j].y) ); if(len <= time*Peo[i].s) Add(i,j); } } int ans = solve(); printf("Scenario #%d: %d ", cas ++, ans); } return 0; } /* 3 1 0 1 1 0 1 0 1 0 */