题解 HDU2063 过山车

题面链接

HDU 2063

Vjudge

题意概述

求一个二分图最大匹配的边数

题目标签

匈牙利算法模板题

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000 + 10
int n, m, k, head[maxn], link[maxn], cnt, tot;
bool vis[maxn];
struct Edge
{
	int to, nxt;
}edge[maxn];
void add(int u, int v)
{
	edge[cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
	cnt++;
}
bool dfs(int u) //深搜判断对于点集v2中的一个点u是否能与点集v1中的一个点v匹配
{
	for(int i = head[u]; i != -1; i = edge[i].nxt){ //枚举能匹配的点
		int v = edge[i].to; //v为能与u匹配的点编号
		if(vis[v]) continue; //利用一个vis判断当前点是否尝试匹配过,如果已经匹配过就跳过以防死循环
		vis[v] = true;
		if(link[v] == -1 || dfs(link[v])){ //如果v可以腾出位置(即没有与v2中的任何一个点匹配或v2中还存在没有匹配过的点可以与之匹配)
			link[v] = u; //u与v成功匹配
			return true;
		}
	}
	return false;
}
int getcp(int n){
	int ans = 0;
	memset(link, -1, sizeof(link));
	for(int i = 1; i <= n; i++){ //遍历每个点集v2中的点
		memset(vis, false, sizeof(vis));
		if(dfs(i)) ans++;
	}
	return ans;
}
int main(){
	while(scanf("%d", &k) != EOF){
		if(!k) break;
		scanf("%d%d", &m, &n);
		memset(head, -1, sizeof(head));
		cnt = 0;
		for(int i = 1; i <= k; i++){
			int u, v;
			scanf("%d%d", &u, &v);
			v += m; //把点集v1中的点的编号调整到点集v2后面
			add(u, v);
		}
		printf("%d\n", getcp(m));
	}
	return 0;
}

参考博文

想理解匈牙利算法的概念,推荐阅读趣写算法系列之–匈牙利算法(推荐在教练的陪同下阅读)

评论区有朋友通俗易懂地概括了它的思想:先到先得 能让就让

hdu 2063 过山车 (匈牙利算法模板题) – 111qqz的小窝


编辑记录

2021-08-05 13:37:00

未经许可禁止任意形式的商业或非商业转载。
点击这里在 Feeds Pub 上订阅本站
主站由 Vercel 驱动,如遇主站无法访问请尝试访问这些镜像:GitHub PagesCloudflare PagesNetlify(应该能实时同步)。
由于静态站点 + Serverless 部署的局限性,我引入了 Google Analytics 来收集访问数据;这些数据只是我自己看着玩的,不会被泄露;
您大可屏蔽它的 Cookie,这不会影响您浏览本站的所有内容或发表评论。
本站通过 Cloudflare Proxy 支持 IPv6 访问,但有时 Proxy 导致证书无法更新等问题时可能会关闭,届时请尝试访问镜像。
萌ICP备 20213003号
Built with Hugo
主题 StackJimmy 设计