搜索与图论:匈牙利算法

这篇具有很好参考价值的文章主要介绍了搜索与图论:匈牙利算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

将所有点分成两个集合,使得所有边只出现在集合之间,就是二分图

二分图:一定不含有奇数个点数的环;可能包含长度为偶数的环, 不一定是连通图文章来源地址https://www.toymoban.com/news/detail-714599.html

二分图的最大匹配:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;//邻接表
bool st[N];
int match[N];

void add(int a , int b)
{//头插法
    //如图 如1与2之间要有一条线,让2的ne为1,再让h[1]为2的索引。
    //这样h[1]就是1节点存的最后一个相连的点,如图就是7节点。
    //而在索引表内部,通过头插法的方式(即每次ne指向上一个点(h存的就是上一个点)),索引表为:7->4->2
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了,这里预定是防止她男朋友找其他喜欢的女孩时不重复找这个
            //如果女孩j没有男朋友,或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&n1,&n2,&m);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }

    int res = 0;
    for(int i = 1; i <= n1 ;i ++)
    {  
        //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
        memset(st,false,sizeof st);
        if(find(i)) res++;//找到一条边,则res++
    }  

    printf("%d\n",res);
}

到了这里,关于搜索与图论:匈牙利算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【匹配】匈牙利匹配算法

    every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?type=blog 匈牙利匹配算法 二分图 顶点分为两个集合, 集合间顶点相连,集合内点不相连 匹配 一个匹配就是一个边的集合,其中, 任意两条边不存在公共的顶点 最大匹配 上图中,我们能找到多组匹配,在

    2024年04月27日
    浏览(35)
  • 指派问题与匈牙利算法

    有n项不同的工作或任务,需要n个人去完成,要求每人只完成一项工作。由于每人的知识、能力、经验等不同,故各人完成不同任务所需的时间不同。问应指派何人完成何项工作,使完成n项工作总耗时最少。这就是指派问题,指派问题也是整数规划问题。 目标函数是最小化问

    2024年02月05日
    浏览(40)
  • 二分图最大匹配——匈牙利算法详解

    关于二分图的基本知识见:二分图及染色法判定 一位红娘近日遇到一群暧昧男女,被请求成全他们,经验丰富的红娘观察到 一名男生可能有多名青睐的女生,一名女生也可能有多名青睐的男生 ,但是出于道德伦理要求,显然只能两两男女配对,为了尽可能使大家满意,她要

    2024年01月21日
    浏览(46)
  • 数学建模(四)整数规划—匈牙利算法

    目录 一、0-1型整数规划问题 1.1 案例 1.2 指派问题的标准形式 2.2 非标准形式的指派问题 二、指派问题的匈牙利解法  2.1 匈牙利解法的一般步骤 2.2 匈牙利解法的实例 2.3 代码实现 投资问题: 有600万元投资5个项目,收益如表,求利润最大的方案? 设置决策变量: 模型: 指派

    2024年02月11日
    浏览(42)
  • DETR | 基于匈牙利算法的样本分配策略

    如有错误,恳请指出。 前不久,沐神对DETR进行了讲解,其实之前也对DETR进行了介绍,见:论文阅读笔记 | 目标检测算法——DETR。现对DETR的核心内容进行重温,也就是其所提出的目标检测的end-to-end框架,输入的是一张图像,输出的直接是最后的预测标注结果,不再需要后处

    2024年02月11日
    浏览(39)
  • AcWing 372. 棋盘覆盖(二分图&&匈牙利算法)

    输入样例: 输出样例: 解析:         n为100,状压肯定爆。         将每个骨牌看成二分图的一个匹配,即查找二分图的一个最大匹配,匈牙利算法。

    2024年02月14日
    浏览(37)
  • AcWing 379. 捉迷藏(最小路径点覆盖&&匈牙利算法)

    输入样例: 输出样例:

    2024年02月14日
    浏览(38)
  • 数学建模笔记——整数规划类问题之我见(匈牙利算法)

    目录 浅浅叙述匈牙利算法 基本思路 计算步骤 来一道简单例题 1.1 符号规定 1.2目标函数​编辑       1.3约束条件 ​编辑 1.4代码 题目复述 基本假设 问题分析 符号说明  模型的建立与求解 模型建立思路 模型建立的过程 建立0-1整数规划模型  运用匈牙利方法: 代码实现  

    2023年04月11日
    浏览(50)
  • 【二分图】 二分图上匹配问题 和 匈牙利算法正确性说明

    本文讨论无权图 思维上没什么难度,但是文字量却比自己想的要多…… 什么是二分图上的匹配?什么是匈牙利算法?   “二分图最大匹配概念、匈牙利算法” 这里引用 Pecco 的介绍。这篇文章写的非常通俗易懂,而且揭示了匈牙利算法(或者说增广路)的本质是“朴素的

    2024年02月13日
    浏览(36)
  • 匈牙利法的Matlab代码及测试

    2024年02月11日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包