二分图-程序员宅基地

二分图：节点由两个集合组成，且两个集合内部没有边的图。换言之，存在一种方案，将节点划分成满足以上性质的两个集合。

染色法

目的：验证给定的二分图是否可以进行二色染色

时间复杂度是 O(n+m)

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

题目：

860. 染色法判定二分图 - AcWing题库https://www.acwing.com/problem/content/862/

匈牙利算法

我们可以看做一个月老在牵红线，现在左边是男生，右边是女生，互相都有心仪的对象，我们就要尽量每一个男生都好。然后就出现了一个图。

我们先看第一个男生，他有两个心仪的对象，先看第一个女生，还是单身，那就选第一个，然后看下一位，也是第一个单身，就她了。但是第三位男生就出问题了，他只有一位心仪的对象，但是呢，那位已经有对象了，但是这位男生还是不放弃，找到那个男朋友，说：“要不你换一换”。我们再一看，确实还有一个备胎单身，就换一个，这样两个人都好，最后一个也很正常，直接匹配。所以总结出十六字真言：待字闺中，据为己有；名花有主，求他放手。 所以说这也告诉我们~~不要轻易放弃，最后悔的不是做错，而是错过。~~

时间复杂度 O(n*m)，实际运形时间远小于n*m

int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}

题目：

861. 二分图的最大匹配 - AcWing题库https://www.acwing.com/problem/content/863/

本文链接：https://blog.csdn.net/weixin_73225182/article/details/137016509

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Android Studio JNI代码突然无法跳转_android studio jni 类无法自动跳转-程序员宅基地

文章浏览阅读4.5k次。Android Studio JNI代码突然无法跳转AndroidStudio3.2 + gradle 4.6 下突然无法是用 ctrl + 左键跳转代码。选中代码点击时出现 “Cannot find declaration to go to” 提示. 经过了换 SDK 后比对发现，如果JNI 代码出现这个问题，一般就是 CMake 版本不对。我换成3.6.xxx就好用了。3.10.xxx不知..._android studio jni 类无法自动跳转

【集成学习-组队学习】3.优化基础模型_模型选择逐步法-程序员宅基地

文章浏览阅读216次。优化基础模型在回归问题的基本算法中，我们使用数据集去估计模型的参数，如线性回归模型中的参数w，那么这个数据集我们称为训练数据集，简称训练集。我们在回归问题中使用训练集估计模型的参数的原则一般都是使得我们的损失函数在训练集达到最小值，其实在实际问题中我们是可以让损失函数在训练集最小化为0，如：在线性回归中，我加入非常多的高次项，使得我们模型在训练集的每一个数据点都恰好位于曲线上，那这时候模型在训练集的损失值也就是误差为0。那么这样我们的模型是否就可以预测任意情况呢？答案是显然否定的。我们建立机器学习_模型选择逐步法

程序设计分组训练实验2实验报告_程序分组训练实验二-程序员宅基地

文章浏览阅读81次。程序设计分组训练实验2_程序分组训练实验二

图书信息管理系统C++_{if(!strcmp(name,book[i].name))-程序员宅基地

文章浏览阅读2k次，点赞4次，收藏45次。实验要求：实验代码；#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <fstream>#include <iomanip>#include <ctype.h>using namespace std;//图书结构体struct Book { double price; ._{if(!strcmp(name,book[i].name))

vue-cli不同版本对比(vue-cli2/cli3/cli4)_vuecli4版本哪个好-程序员宅基地

文章浏览阅读2.1k次，点赞7次，收藏11次。版本/操作vue-cli2vue-cli3/cli4vue-cli下载安装 npm install vue-cli -g npm install -g vue@cli创建新项目vue init webpack 2.0projectvue create 3.0project启动项目npm run devnpm ru..._vuecli4版本哪个好

linux内核添加usb键盘驱动,配置USB外设 - linux-2.6.32在mini2440开发板上移植_Linux编程_Linux公社-Linux系统门户网站...-程序员宅基地

文章浏览阅读902次。linux-2.6.32在mini2440开发板上移植配置USB外设[日期：2013-04-08]来源：Linux社区作者：ssdsafsdsd[字体：大中小]编者：因为LINUX内核对S3C2440的Host驱动的已经支持，而且支持的外设相当的丰富，所以这一部分只是进行配置就可以使用。因为配置的东西较多，没有给出详细的截图，看手册上介绍的就很明白。需要手册的请留下邮箱索取。1 配置和测试US..._linux内核识别鼠标需要开启什么配置

随便推点

【解决windows install问题】如找不到vc_runtimeMinimum_x86.msi，如强制删除软件方法-程序员宅基地

文章浏览阅读169次。其中卸载软件可能卸载不掉，用下面这个软件进行卸载(万能)_vc_runtimeminimum_x86

java核心技术卷1 第11版勘误表_java核心技术第11版关于takewhile的介绍有错-程序员宅基地

文章浏览阅读505次。11th Edition Volume 1 (Java SE 9 - 11)Page 54Change “Except, of course, when n is negative.” to “Except, of course, when n is odd and negative.”Page 69Change the method names empty and blank to isEmpty and isBlank.Page 69In the API note for the start_java核心技术第11版关于takewhile的介绍有错

前端八股（基于黑马八股文档的二次总结）-程序员宅基地

文章浏览阅读611次，点赞28次，收藏12次。精灵图是把网站上用到的一些图片整合到一张单独的图片中，从而减少你的网站的 HTTP 请求数量，该图片使用 css background 和 background-position 属性渲染，这也就意味着你的标签变得更复杂了，图片是在 css 中定义，并非在1、减少网页的 http 请求，从而加快了网页加载速度，提高用户体验2、减少图片的体积，因为每个图片都有一个头部信息，把多个图片放到一个图片里，就会共用同一个头信息，从而减少了字节数。

关于使用LTC6811/LTC6804断线自检的一些心得-程序员宅基地

文章浏览阅读649次，点赞11次，收藏17次。说起来惭愧，这个问题最初是还是客户先发现的，当时做的是一款用在两厢纯电动(品牌这里就不说了)上面的一体机，总压40串，使用了4片LTC6811-2。前期在家里做断线测试都是“静态”的，没考虑到“动态”的情况，而且当时的关注点都在检测的速度上，客户要求断线告警上报时间不能超过6S。当然为了确保系统正常工作，必须要有一定的自检功能，楼主使用了“命令组”自检、被动均衡自检和断线自检，其中在使用断线自检遇到一个问题，现在将这个问题和大家分享下，共同学习。_ltc6811

android 收藏歌曲功能,基于android的网络音乐播放器-回调实现音乐播放及音乐收藏的实现（三）...-程序员宅基地

文章浏览阅读978次。作为android初学者，最近把疯狂android讲义和疯狂Java讲义看了一遍，看到书中介绍的知识点非常多，很难全部记住，为了更好的掌握基础知识点，我将开发一个网络音乐播放器-EasyMusic来巩固下，也当作是练练手。感兴趣的朋友可以看看，有设计不足的地方也欢迎指出。开发之前首先介绍下该音乐播放器将要开发的功能(需求)：1.本地音乐的加载和播放；2.网络音乐的搜索，试听和下载；3.音乐的断点下..._android收藏本地音乐原创

项目：电子词典_aggressor bump-程序员宅基地

文章浏览阅读2.6w次。项目：电子词典_aggressor bump