首页 > 编程语言 >【学习笔记】匈牙利算法

【学习笔记】匈牙利算法

时间:2022-09-21 08:22:49浏览次数:84  
标签:二分 ch int 匈牙利 while 笔记 算法 include getchar

【图论】二分图最大匹配——匈牙利算法

二分图

相当好理解

这是百度百科的定义

二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图

听不懂吧

其实就是一个图能正好分成两部分,每个部分内的点互相没有边就是二分图

二分图的判定

用两种颜色,让相连的点的颜色不同就好啦

如果要染色的点已经有颜色了,并且和当前这个点的颜色相同,那么说明发生了矛盾,也就是这张图不是二分图

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=1e5+5;

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}

bool check;

int n,m;

int tot;

int col[maxn];

int head[maxn];

struct edge
{
	int to;
	int next;
}e[maxn*2];

void add(int x,int y)
{
	tot++;
	e[tot].to=y;
	e[tot].next=head[x];
	head[x]=tot;
}

bool dfs(int x,int c)
{
	col[x]=c;
	
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		
		if(!col[to])
		{
			if(dfs(to,-c))
			{
				return true;
			}
		}
		else if(col[to]==c)
		{
			return true;
		}
	}
	
	return false;
}

int main()
{
	n=read();
	m=read();
	
	for(int i=1;i<=m;i++)
	{
		int u=read();
		int v=read();
		add(u,v);
		add(v,u);
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!col[i])
		{
			check=dfs(i,1);
		}
		if(check==true)
		{
			break;
		}
	}
	
	if(check)
	{
		cout<<"No";
	}
	else
	{
		cout<<"Yes";
	}
	
	return 0;
}

二分图最大匹配

匈牙利算法

很简单啦

先枚举左部点u,然后和右边的v匹配,如果当前的匹配的这个右部点v已经和另一个左部点w匹配了,就让原来匹配的左部点w换一个(他会同意的,除非他没有其他选择了),如果w没得换那u只能单着了(可怜)

代码很短,就是个dfs

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=5e4+5;

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}

int tot,ans;

int head[maxn];

int n,m,num_e;

int match[maxn];

bool vis[maxn];

struct edge
{
	int to;
	int next;
}e[maxn];

void add(int x,int y)
{
	tot++;
	e[tot].to=y;
	e[tot].next=head[x];
	head[x]=tot;
}

bool dfs(int x)
{
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		
		if(!vis[to])
		{
			vis[to]=true;
			
			if(!match[to] || dfs(match[to]))
			{
				match[to]=x;
				return true;
			}
		}
	}
	
	return false;
}

int main()
{
	n=read();
	m=read();
	num_e=read();
	
	for(int i=1;i<=num_e;i++)
	{
		int u=read();
		int v=read();
		add(u,v);
	}
	
	for(int i=1;i<=n;i++)
	{
		memset(vis,false,sizeof(vis));
		if(dfs(i))
		{
			ans++;
		}
	}

	cout<<ans;
	
	return 0;
}

生まれつき何も持っていないからこそ、私たちはすべてを持つことができます

标签:二分,ch,int,匈牙利,while,笔记,算法,include,getchar
From: https://www.cnblogs.com/SitoASK/p/16714324.html

相关文章

  • SpringMVC学习笔记(五)
    注解配置MVC使用配置类和注解联合使用的方式代替xml配置文件 在Servlet3.0环境中,容器会在类路径中查找实现javax.servlet.ServletContainerInitializer接口的类,如果找......
  • 密码学基础之非对称加密算法
    非对称加密算法非对称加密的一般流程是服务端生成一个密钥对(私钥和公钥),然后将公钥发送给客户端。之后服务可以通过私钥加密数据发送给客户端,客户端收到消息后通过公钥解密......
  • 字符编码笔记:ASCII,Unicode 和 UTF-8
    一、ASCII码我们知道,计算机内部,所有信息最终都是一个二进制值。每一个二进制位(bit)有0和1两种状态,因此八个二进制位就可以组合出256种状态,这被称为一个字节(byte)。也就是说......
  • 积性函数笔记
    积性函数:定义设f(n)为积性函数,n=ab且(a,b)=1,有f(n)=f(a)*f(b)完全积性函数n=ab,即有f(n)=f(a)*f(b),不要求(a,b)=1;常见函数\(\epsilon,\phi,d,\sigma,I,\mu,Id\)迪......
  • MySQL数据库笔记
    1.操作数据库1.1创建数据库createdatabase数据库名如果想数据库没有就创建,有就不创建可以执行这句话sqlcreatedatabaseifnotexists数据库名1.2删除数据库......
  • 算法竞赛模板
    常用模板#pragmaGCCoptimize(3)#include<bits/stdc++.h>//=============全局LL================#defineintlonglong//=============全局LL==============......
  • Java学习笔记---JDK8新特性(Lambda表达式)
    1.Lambda表达式基础格式:()->{};//()为lambda表达式的参数//->为箭头操作符//{}为lambda方法体lambda表达式结果为一个实例对象,用于直接实例化......
  • 《人工智能》李开复版读书笔记
    前言:本读书笔记大多为摘录,是我认为非常有价值的部分。欲知详情,还请阅读原书。 如今,人工智能已经无处不在。手机上的常见应用,大多使用了人工智能技术,例如图像处理与机器......
  • CSP 2022 备战 高精度算法
    在考场上,有些题目,你用int只能拿30分开了longlong还是会爆这时候还得靠高精度算法来支持概念:将数字中的每一位存入数组中比如123,可以将它存入一个a[3]的数组中a[0]......
  • Vin-Mono论文阅读笔记(二)
    估计器初始化简述单目紧耦合VIO是一个高度非线性的系统,需要在一开始就进行准确的初始化估计。通过将IMU预积分与纯视觉结构进行松耦合对齐,我们得到了必要的初始值。理解:......