当前位置：首页 > news >正文

HDU-2389 Rain on your Parade(二分图之Hopcroft-Karp算法)

news 来源：原创 2024/5/7 4:03:14

题意：

N个人M把伞，T秒后下雨，给出每个人的坐标和跑路的速度以及伞的坐标，问在T秒内最多能有几个人能拿到伞（约束：每把伞只能一个人用）。(N,M <= 3000)

思路：

很容易看出来的最大匹配，但发现点的数量达到3000，而边的数量也随之达到3000*3000，而匈牙利算法的复杂度为O(N*M)[N是A部的点数,M是边数]。所以这里引出了一个复杂度为O(sqrt(N)*M)的Hopcroft-Karp算法，入门点击。

代码(模板)：

#include <algorithm>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3005;
struct node
{
	int x, y, d;
} a[maxn];
vector<int> G[maxn];
int T, N, M;
int nx, ny;		//A部点数，B部点数 
int dx[maxn], dy[maxn], cx[maxn], cy[maxn];
//A部层次，B部层次，A部匹配的B部点，B部匹配的A部点 
int dis, vis[maxn];
queue<int> q;
bool BFS()
{
	memset(dx, -1, sizeof dx);
	memset(dy, -1, sizeof dy);
	while(!q.empty()) q.pop();
	dis = inf;
	for(int i = 1; i <= nx; ++i)
	if(cx[i] == -1) q.push(i);	//每次都以A部未匹配的点为起点 
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		if(dx[u] > dis) break;	//寻诈增广路终止条件：第K层包含为匹配的B部顶点 
		for(int i = 0; i < G[u].size(); ++i)
		{
			int v = G[u][i];
			if(dy[v] == -1)
			{
				dy[v] = dx[u]+1;
				//确定当找到B部未匹配点时的层次 
				if(cy[v] == -1) dis = dy[v];
				else
				{
					//通过已匹配边直接寻到A部的点 
					dx[cy[v]] = dy[v]+1;
					q.push(cy[v]);
				}
			}
		}
	}
	return dis != inf;
}
int DFS(int cur)
{
	for(int i = 0; i < G[cur].size(); ++i)
	{
		int v = G[cur][i];
		if(!vis[v] && dy[v] == dx[cur]+1)
		{
			vis[v] = 1;
			//当第dis层的B部点不是未匹配点时，直接忽略(优化) 
			if(cy[v] != -1 && dy[v] == dis) continue;
			if(cy[v] == -1 || DFS(cy[v]))
			{
				cy[v] = cur;
				cx[cur] = v;
				return 1;
			}
		}
	}
	return 0;
}
int hopcroft_karp()
{
	memset(cx, -1, sizeof cx);
	memset(cy, -1, sizeof cy);
	int ans = 0;
	while(BFS())
	{
		memset(vis, 0, sizeof vis);
		for(int i = 1; i <= nx; ++i)
		if(cx[i] == -1) ans += DFS(i);
	}
	return ans;
}
int judge(int x1, int y1, int x2, int y2, int d)
{
	return (d*T*d*T) >= (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
void mapping()	//构图 
{
	int x, y;
	scanf("%d %d", &T, &M);
	for(int i = 1; i <= M; ++i)
	{
		G[i].clear();
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].d);
	}
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
	{
		scanf("%d %d", &x, &y);
		for(int j = 1; j <= M; ++j)
		{
			if(judge(x, y, a[j].x, a[j].y, a[j].d))
			G[j].push_back(i);
		}
	}
}
int main()
{
	int tt; scanf("%d", &tt);
	for(int _ = 1; _ <= tt; ++_)
	{
		mapping();
		nx = M, ny = N;
		int ans = hopcroft_karp();
		printf("Scenario #%d:\n%d\n\n", _, ans);
	}
	return 0;
}

继续加油~