您现在的位置是:首页 > 正文

二分图相关

2024-01-30 21:10:36阅读 0

二分图相关

一、染色法判定二分图

二分图要求边的两端点处于不同的集合,那么将两端点分别染成不同的颜色,如果没有冲突,则说明是二分图。

首先是dfs函数,深搜进行染色:

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])
        {
            if(!dfs(j,3 - c))return 0;//color函数表示颜色,用1和2染色,0表示未染色(颜色变化3 - 1 = 2,3 - 2 = 1)
        }
        else if(color[j] == c) return 0;//如果染色相同,则冲突
    }
    
    return 1;
} 

由于存在多个连通块,则需要遍历每个点:

bool flag = 1;
	for (int i = 1; i <= n; i++)
	{
		if (!color[i])
		{
			if (!dfs(i, 1))
			{
				flag = 0;
				break;
			}
		}
	}

二、二分图的最大匹配

二分图的最大匹配利用的是匈牙利算法,代码如下:

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

遍历一个集合的所有点即可,最后的ans就是最大匹配:

int ans = 0;
for(int i = 1;i <= n1;i++)
{
    memset(vis,0,sizeof vis);
    if(xyl(i))ans++;
}

网站文章

  • 在ML中缺乏数据可是个大问题,亲测有效的5种方法帮您解决

    在ML中缺乏数据可是个大问题,亲测有效的5种方法帮您解决

    https://www.toutiao.com/a6701193162699833859/ 在我做过的很多项目中,公司虽然有非常棒的AI商业创意,但当他们意识到自己没有足够的数据时,却会慢慢的变得沮丧起来。然而,确实有解决的方案。本文的目的是简要地向你介绍其中的一些在我的实践中已经证明有效的方法,而不是列出所有现有的解决方案。 数据稀缺问题非常重要,因为数据是任何人工智能项目的...

    2024-01-30 21:10:30
  • JavaWeb学习笔记——jQuery动画、事件

    jQuery-3动画方法练习:品牌显示事件文档加载事件绑定事件移除事件冒泡事件对象练习:图片跟随 动画 方法 基本: show([speed,[easing],[fn]]) 显示 hide([spee...

    2024-01-30 21:10:01
  • 结构体变量

    在C语言中,可以使用结构体(Struct)来存放一组不同类型的数据。结构体的定义形式为: struct 结构体名{ 结构体所包含的变量或数组 }; 结构体是一种集合,它里面包含了多个变量或数组,它们的...

    2024-01-30 21:09:56
  • Java面试注意

    3125

    2024-01-30 21:09:48
  • python 依赖下载

    https://www.lfd.uci.edu/~gohlke/pythonlibs/#scipy

    2024-01-30 21:09:20
  • 轻松学懂图(下)——Dijkstra和Bellman-Ford算法

    轻松学懂图(下)——Dijkstra和Bellman-Ford算法

    概述 在上一篇文章中讲述了Kruskal和Prim算法,用于得到最小生成树,今天将会介绍两种得到最短路径的算法——Dijlkstra和Bellman-Ford算法 Dijkstra算法 算法的特点: ...

    2024-01-30 21:09:14
  • 顺序队列的基本操作实现

    顺序队列的基本操作

    2024-01-30 21:09:08
  • 电脑桌面计算机打开不显示硬盘信息,电脑加硬盘后不显示不出来怎么办

    1.给电脑添加了一个新硬盘,可是显示不出来怎么办1、在计算机上安装硬盘后,打开计算机,在计算机桌面上,选择我的计算机并右键单击“管理”进入计算机管理界面。2、选择“磁盘管理”,系统将弹出来检测新硬盘并...

    2024-01-30 21:09:00
  • 欢迎使用CSDN-markdown编辑器

    项目Properties -> Project Facets -> Runtime -> New -> Add a tomcat server ,JRE 选择 JRE1.8.0_XX.

    2024-01-30 21:08:31
  • LinkedBlockingQueue的put,take方法

    put操作:在LinkedBlockingQueue中有putlcok和takelock俩把锁,put操作使用putlock这把锁,利用lockInterruptibly方法加锁,该方法的作用为:如果...

    2024-01-30 21:08:18