做动态头像的网站,做商城网站用什么框架,上海外贸仓库,wordpress 页面 关闭评论题目来源
Problem - 2063 (hdu.edu.cn) 题目描述
RPG girls今天和大家一起去游乐场玩#xff0c;终于可以坐上梦寐以求的过山车了。
可是#xff0c;过山车的每一排只有两个座位#xff0c;而且还有条不成文的规矩#xff0c;就是每个女生必须找个男生做partner和她同坐…题目来源
Problem - 2063 (hdu.edu.cn) 题目描述
RPG girls今天和大家一起去游乐场玩终于可以坐上梦寐以求的过山车了。
可是过山车的每一排只有两个座位而且还有条不成文的规矩就是每个女生必须找个男生做partner和她同坐。
但是每个女孩都有各自的想法举个例子把
Rabbit只愿意和XHD或PQK做partnerGrass只愿意和linle或LL做partnerPrincessSnow愿意和水域浪子或伪酷儿做partner
考虑到经费问题boss刘决定只让找到partner的人去坐过山车其他的人嘿嘿就站在下面看着吧。
聪明的Acmer你可以帮忙算算最多有多少对组合可以坐上过山车吗 输入描述
输入数据的第一行是三个整数K , M , N分别表示可能的组合数目女生的人数男生的人数。
0 K ≤ 10001 ≤ N, M ≤ 500
接下来的K行每行有两个数分别表示女生 Ai 愿意和男生 Bj 做partner。
最后一个0结束输入。 输出描述
对于每组数据输出一个整数表示可以坐上过山车的最多组合数。 用例
输入6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0输出3 题目解析
本题是二分图最大匹配问题。 首先我们需要知道什么是二分图
二分图是一种特殊的图结构二分图中的节点可以分为两部分每个部分中的节点之间互不相连比如下图所示 绿色点集是一个部分橙色点集是一个部分各个部分中节点之间互不相连 二分图的 匹配 指的是 边的集合“匹配中的各个边之间没有共同节点即每个边都是独立的。
比如下图中的两个红色边就形成了一个匹配因为1-4边2-5边之间没有共同节点两个边是互相独立的。 二分图的最大匹配指的是边最多的匹配比如下图中1-5边2-6边3-4边之间互相独立可以形成一个数量为3条边的匹配。下面二分图最多只能有3条边的匹配。 那么如何求二分图的最大匹配呢 最常用的办法就是匈牙利算法。
在解释匈牙利算法之前我们需要先对二分图最大匹配问题的实际意义做一个解释。 比如现在有男生若干女生若干而每个男生都有心仪的多个女生每个女生也有心仪的多个男生而男生、女生只会和心仪的对象进行配对现在需要实现最大配对 上面例子就是二分图最大匹配的典型应用。 我们假设节点123是男生456是女生那么初始时存在如下心仪关系
1 和 4 互相心仪1 和 5 互相心仪2 和 5 互相心仪2 和 6 互相心仪3 和 4 互相心仪
因此可得二分图如下 下面开始演示匈牙利算法来找到最大匹配数
我们需要选择二分图的一部分作为发起配对请求的一方比如我们选择男生作为发起配对请求的一方此时遍历每一个男生
假设先遍历出男生1而男生1和与女生4女生5互相心仪此时我们可以任选一个女生进行配对比如选择女生4进行配对由于女生4当前没有配对对象因此男生1和女生4可以配对成功 男生1完成配对后继续遍历下一个男生2发起配对请求而男生2和女生5女生6互相心仪此时我们可以任选一个女生进行配对比如选择女生5进行配对由于女生5当前没有配对对象因此男生2和女生5可以配对成功 男生2完成配对后继续遍历下一个男生3发起配对请求而男生3只和女生4互相心仪但是女生4已经和男生1配对了 此时为了实现最大配对我们只能委屈男生1让他找一找其他可以配对的女生然后发现男生1还和女生5互相心仪因此我们尝试将男生1和女生5配对。 但是女生5已经和男生2发生配对了 因此为了实现最大配对只能委屈男生2找找看其他可以配对的女生然后发现男生2还和女生6互相心仪因此尝试将那是2和女生6进行配对 而女生6没有发生过配对因此男生2可以和女生6成功配对。
由于男生2和女生6成功配对了因此虚线2-6变为实线而一个男生只能和一个女生配对因此实线2-5变为虚线 而由于女生5和男生2解除了配对状态因此男生1和女生5就可以成功配对因此1-5从虚线变为实线而一个男生只能和一个女生配对因此实线1-4变为虚线 由于女生4和男生1解除了配对状态因此男生3和女生4可以成功配对因此虚线3-4变为实线 此时我们完成了所有男生的配对即得到了最大匹配。 上面从配对情况图中黑虚线和红实线逆变为黑实线和红虚线实现了配对数1
如下图左边只有两个配对红色线右边有三个配对黑色线 我们将左边这种展开为“虚实虚实虚”的情况称为增广路增广路的特点是两端为虚中间虚实交替增广路的逆变可以实现配对数1。
关于增广路的定义和意义就是如此了解即可。 以上就是匈牙利算法的实现过程。总结一下就是
初始时寻找一方作为配对发起方比如男生遍历每一个男生发起配对请求
男生a只能对互相心仪的女生发起配对请求
如果互相心仪的女生b没有发生过配对则和当前男生配对成功如果互相心仪的女生b已经发生了配对那么需要找到女生b的配对对象男生c并尝试让男生c重新找一个可以配对的其他女生此时为递归重复逻辑即男生c对其他互相心仪的女生发起配对请求如果最终男生c可以配对其他女生则男生a与女生b配对成功否则男生a与女生b无法配对。
按照上面逻辑我们让每一个男生都发起配对请求最终我们可以找到最大匹配数。 更多细节请看下面代码实现。 Java算法源码
import java.util.Arrays;
import java.util.Scanner;public class Main {static int m;static int n;static boolean[][] edges;static int[] match;static boolean[] vis;public static void main(String[] args) {Scanner sc new Scanner(System.in);while (sc.hasNextInt()) {int k sc.nextInt();if (k 0) break;m sc.nextInt(); // m个女生n sc.nextInt(); // n个男生// edges[a][b] true 表示 a女生 和 b男生 可以配对edges new boolean[m 1][n 1];for (int i 0; i k; i) {int a sc.nextInt();int b sc.nextInt();edges[a][b] true;}// match[b] 表示男生b配对的女生match new int[n 1];// vis[b] 表示男生b是否在本次增广路中vis new boolean[n 1];// ans记录题解int ans 0;// 遍历女生afor (int a 1; a m; a) {// 从女生a开始进行增广路探索探索前需要将vis重置Arrays.fill(vis, false);// 如果a找到配对男生则配对边1if (dfs(a)) ans;}System.out.println(ans);}}public static boolean dfs(int a) {// 遍历男生bfor (int b 1; b n; b) {// 如果男生b不在女生a发起的探索的增广路中且a,b可以配对if (!vis[b] edges[a][b]) {// 则当前增广路加入男生bvis[b] true;// 如果男生b没有被其他人配对 || 已经和其他人配对但是男生b当前配对的女生match[b]可以放弃男生b而和其他男生配对if (match[b] 0 || dfs(match[b])) {// 则男生b可以和女生a配对即配对成功match[b] amatch[b] a;return true;}}}return false;}
}JS算法源码
const rl require(readline).createInterface({ input: process.stdin });
var iter rl[Symbol.asyncIterator]();
const readline async () (await iter.next()).value;void (async function () {// m个女生, n个男生, k条边const [k, m, n] (await readline()).split( ).map(Number);// edges[a][b] true 表示 a女生 和 b男生 可以配对const edges new Array(m 1).fill(0).map(() new Array(n 1).fill(false));for (let i 0; i k; i) {const [a, b] (await readline()).split( ).map(Number);edges[a][b] true;}await readline(); // 读取最后一行输入的0// match[b] 表示男生b配对的女生const match new Array(n 1).fill(0);// vis[b] 表示男生b是否在本次增广路中const vis new Array(n 1).fill(false);// ans记录题解let ans 0;// 遍历女生afor (let a 1; a m; a) {// 从女生a开始进行增广路探索探索前需要将vis重置vis.fill(false);// 如果a找到配对男生则配对边1if (dfs(a)) ans;}function dfs(a) {// 遍历男生bfor (let b 1; b n; b) {// 如果男生b不在女生a发起的探索的增广路中且a,b可以配对if (!vis[b] edges[a][b]) {// 则当前增广路加入男生bvis[b] true;// 如果男生b没有被其他人配对 || 已经和其他人配对但是男生b当前配对的女生match[b]可以放弃男生b而和其他男生配对if (match[b] 0 || dfs(match[b])) {// 则男生b可以和女生a配对即配对成功match[b] amatch[b] a;return true;}}}return false;}console.log(ans);
})();Python算法源码
# 输入获取
k, m, n map(int, input().split()) # k个配对, m个女生, n个男生edges [[False] * (n 1) for _ in range(m 1)]
for _ in range(k):a, b map(int, input().split())edges[a][b] True # edges[a][b] true 表示 a女生 和 b男生 可以配对input()match [0] * (n 1) # match[b] 表示男生b确定配对的女生def dfs(a, vis):# 遍历男生bfor b in range(1, n 1):# 如果男生b不在女生a发起的探索的增广路中且a,b可以配对if not vis[b] and edges[a][b]:# 则当前增广路加入男生bvis[b] True# 如果男生b没有被其他人配对 || 已经和其他人配对但是男生b当前配对的女生match[b]可以放弃男生b而和其他男生配对if match[b] 0 or dfs(match[b], vis):# 则男生b可以和女生a配对即配对成功match[b] amatch[b] areturn Truereturn False# 算法入口
def getResult():ans 0for a in range(1, m 1):# vis[b] 表示男生b是否在a女生发起的增广路探索中vis [False] * (n 1)# 如果a找到配对男生则配对边1if dfs(a, vis):ans 1return ans# 算法调用
print(getResult())C算法源码
#include stdio.h#define MAX_SIZE 501#define TRUE 1
#define FALSE 0int m, n; // m个女生, n个男生
int edges[MAX_SIZE][MAX_SIZE]; // edges[a][b] true 表示 a女生 和 b男生 可以配对
int match[MAX_SIZE]; // match[b] 表示男生b配对的女生
int vis[MAX_SIZE]; // vis[b] 表示男生b是否在本次增广路中int dfs(int a) {// 遍历男生bfor (int b 1; b n; b) {// 如果男生b不在女生a发起的探索的增广路中且a,b可以配对if (!vis[b] edges[a][b]) {// 则当前增广路加入男生bvis[b] 1;// 如果男生b没有被其他人配对 || 已经和其他人配对但是男生b当前配对的女生match[b]可以放弃男生b而和其他男生配对if (match[b] 0 || dfs(match[b])) {// 则男生b可以和女生a配对即配对成功match[b] amatch[b] a;return TRUE;}}}return FALSE;
}int main() {while (1) {int k;scanf(%d, k);if (k 0) break;scanf(%d %d, m, n);// 初始化edgesfor (int i 0; i m; i) {for (int j 0; j n; j) {edges[i][j] FALSE;}}// 关联可匹配的男女生for (int i 0; i k; i) {int a, b;scanf(%d %d, a, b);edges[a][b] TRUE;}// 初始化matchfor (int i 0; i n; i) {match[i] 0;}// ans记录题解int ans 0;// 遍历女生for (int a 1; a m; a) {// 初始化visfor (int i 0; i n; i) {vis[i] FALSE;}// 如果女生a找到匹配男生则匹配边if (dfs(a)) {ans;}}printf(%d\n, ans);}return 0;
}
