二分图、匈牙利算法

2024-04-03 14:28
文章标签 算法 二分 匈牙利

本文主要是介绍二分图、匈牙利算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一，二分图

CodeForces 687A NP-Hard Problem

力扣 785. 判断二分图

二，完全二分图

1，完全二分图

2，K2,3

3，K3,3

三，匈牙利算法

1，二分图最大匹配

2，其他图论问题

一，二分图

一般我们研究二分图默认指的是无向图。

二分图是指，可以把图中的顶点分成两个集合，使得每个集合中的所有点之间都是互不相连的。

	//判断是不是二分图, 节点编号是0到n-1static bool isTwoDivGraph(int n, UndirectedGraphData<int> &g) {UnionDif unions(n);for (auto e : g.edges) {unions.find(e.a);unions.find(e.b);if (unions.inSame(e.a, e.b)) {if (int(unions.getDif(e.a) + unions.getDif(e.b)) % 2)return false;}else {unions.merge(e.a, e.b,1);}}return true;}

CodeForces 687A NP-Hard Problem

题目：

Description

Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting.

Suppose the graph G is given. Subset A of its vertices is called a vertex cover of this graph, if for each edge uv there is at least one endpoint of it in this set, i.e.  or  (or both).

Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.

They have agreed to give you their graph and you need to find two disjoint subsets of its vertices A and B, such that both A and B are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively.

Each of the next m lines contains a pair of integers ui and vi (1  ≤  ui,  vi  ≤  n), denoting an undirected edge between ui and vi. It's guaranteed the graph won't contain any self-loops or multiple edges.

Output

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).

If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integer k denoting the number of vertices in that vertex cover, and the second line contains kintegers — the indices of vertices. Note that because of m ≥ 1, vertex cover cannot be empty.

Sample Input

Input

4 2
1 2
2 3

Output

1
2 
2
1 3 

Input

3 3
1 2
2 3
1 3

Output

-1

题目大意就是把图分成二分图，如果不能的话，输出-1，如果能的话，分别输出2个部分的点的数量和点的标号。

代码：

#include<iostream>
#include<string.h>
using namespace std;int list[100005];
int fenzu[100005];int main()
{int n, m;cin >> n >> m;int fx, fy;memset(list, 0, sizeof(list));memset(fenzu, 0, sizeof(fenzu));int x, y;int zu = 1;while (m--){cin >> x >> y;		if (list[x] == 0){if (list[y] == 0){fenzu[x] = zu;fenzu[y] = zu;list[x] = 1;list[y] = 2;zu++;}else{fenzu[x] = fenzu[y];list[x] = 3 - list[y];}}else{if (list[y] == 0){fenzu[y] = fenzu[x];list[y] = 3 - list[x];}else{fx = fenzu[x];fy = fenzu[y];if (fx == fy){if (list[x] == list[y]){cout << "-1";return 0;}}else{					if (list[x] == list[y]){for (int i = 1; i <= n; i++)if (fenzu[i] == fy){fenzu[i] = fx;list[i] = 3 - list[i];}}					else for (int i = 1; i <= n; i++)if (fenzu[i] == fy)fenzu[i] = fx;}}}}int sum = 0;for (int i = 1; i <= n; i++)if (list[i] == 1)sum++;cout << sum << endl;for (int i = 1; i <= n; i++)if (list[i] == 1)cout << i<<" ";cout << endl << n - sum << endl;for (int i = 1; i <= n; i++)if (list[i] != 1)cout << i << " ";return 0;
}

可惜超时了，在test14超时了，test14估计是n和m非常大的了。

前面13个test都过了，想必这个代码是没有问题的，就是效率的问题。

很显然，主要的效率问题就是，在唯一的while循环里面，有1个从1到n的循环，只为了检索一些特定的目标出来。

所以很显然，我应该使用队列。

抛弃这个思想，用队列来做，其实很简单，只要记录每个点的所有邻居即可。

代码：

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;vector<int>v[100005];
queue<int>q;
int list[100005];int main()
{int n, m;cin >> n >> m;int x, y;while (m--){cin >> x >> y;	v[x].insert(v[x].end(),y);v[y].insert(v[y].end(),x);}int k, key = 1;memset(list, 0, sizeof(list));vector< int >::iterator p;while (1){while (list[key])key++;if (key > n)break;q.push(key);list[key] = 1;while (!q.empty()){k = q.front();q.pop();for (p = v[k].begin(); p != v[k].end(); p++){if (list[*p] == list[k]){cout << "-1";return 0;}if (list[*p] == 0){q.push(*p);list[*p] = 3 - list[k];}}}}int sum = 0;for (int i = 1; i <= n; i++)if (list[i] == 1)sum++;cout << sum << endl;for (int i = 1; i <= n; i++)if (list[i] == 1)cout << i<<" ";cout << endl << n - sum << endl;for (int i = 1; i <= n; i++)if (list[i] != 1)cout << i << " ";return 0;
}

表面上有3层循环，实际上外面的2层while循环是有限制的，合起来也就是大约n而已。

里面的循环就更不用说了，3层循环合起来也就是大约n而已。

所以这个算法还是很快的，果然AC了。

力扣 785. 判断二分图

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

提示：

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] 不会包含 u
  • graph[u] 的所有值 互不相同
  • 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

c++代码：

class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {map<int, vector<int>>m;for (int i = 0; i < graph.size(); i++)m[i] = graph[i];UndirectedGraphData<int> g(m);return UndirectedGraph::isTwoDivGraph(m.size(), g);}
};

rust代码：

struct Union{fa:Vec<usize>,dif:Vec<i32>,
}
impl Union{fn find(& mut self,x:usize)->usize{if self.fa[x] == x{return x;}Union::find(self,self.fa[x]);self.dif[x] += self.dif[self.fa[x]];self.fa[x] = self.fa[self.fa[x]];return self.fa[x];}fn in_same(& mut self,x:usize,y:usize)->bool{return Union::find(self,x) == Union::find(self,y);}fn merge(& mut self,x:usize,y:usize,x_sub_y:i32)->(){Union::find(self,x);let fax = self.fa[x];self.dif[fax] = x_sub_y - self.dif[x];self.fa[fax] = y;}
}impl Solution {pub fn is_bipartite(graph: Vec<Vec<i32>>) -> bool {let mut fa=Vec::new();let mut dif=Vec::new();for i in 0..graph.len(){fa.push(i);dif.push(0);}let mut opt = Union{fa:fa,dif:dif};for x in 0..graph.len(){for y in graph[x].clone(){let y = y as usize;if opt.in_same(x, y){if (opt.dif[x]+opt.dif[y])%2 == 0{return false;}}else{opt.merge(x, y, 1);}}}return true;}
}

二，完全二分图

1，完全二分图

完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

2，K2,3

3，K3,3

三，匈牙利算法

1，二分图最大匹配

思路：

从0开始，逐步扩展。

扩展方法：寻找类似于0-1-2-3-4-5的路径，把匹配“1-2 3-4”调整成匹配“0-1 2-3 4-5”，匹配数加1。

示例：

调整前：

寻找路径：

调整后：

模板代码：

参考ACM模板

2，其他图论问题

待更新

这篇关于二分图、匈牙利算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/873164。

相关文章

springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2