问题求解III-HW06 题解
Problem A: 路由规划
- 给定 $n$ 个点 $m$ 条边的带权无向图，求最小生成树。
- $n\leq 5000, m\leq 2\times 10^5$。
最小生成树的模板题。常见的最小生成树算法有 Prim 和 Kruskal。感兴趣的同学可以了解 Boruvka 算法，它在一些具有特殊性质的稠密图上能发挥神奇的作用。
Problem B: 找工作
- 给定左侧 $x$ 个点，右侧 $y$ 个点，共有 $z$ 条边的二分图，求最大匹配。
- $1\leq x, y\leq 10000, 1\leq z\leq 2\times 10^5$。
二分图最大匹配的模板题。本题由于数据规模较大，使用匈牙利算法可能无法通过。希望大家学会 Hopcroft-Karp 算法，或者通过建立超级源点/超级汇点的方式将其转换成最大流问题求解。