• 搜索与图论 ---- 匈牙利算法


    匈牙利算法

    时间复杂度是 O(nm)O(nm), nn 表示点数,mm 表示边数

    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 ++ ;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    861. 二分图的最大匹配

    给定一个二分图,其中左半部包含 n1 个点(编号 1∼n1),右半部包含 n2 个点(编号 1∼n2),二分图共包含 m 条边。

    数据保证任意一条边的两个端点都不可能在同一部分中。

    请你求出二分图的最大匹配数。

    二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E} 中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。

    二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。

    输入格式

    第一行包含三个整数 n1、 n2 和 m。

    接下来 m 行,每行包含两个整数 u 和 v,表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

    输出格式

    输出一个整数,表示二分图的最大匹配数。

    数据范围

    1≤n1,n2≤500,
    1≤u≤n1,
    1≤v≤n2,
    1≤m≤105

    输入样例:
    2 2 4
    1 1
    1 2
    2 1
    2 2
    
    • 1
    • 2
    • 3
    • 4
    • 5
    输出样例:
    2
    
    • 1
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    
    #define x first
    #define y second
    
    using namespace std;
    typedef long long ll;
    typedef pair<int, int> PII;
    const int N = 100010;
    const int MOD = 1000000007;
    const int INF = 0x3f3f3f3f;
    
    int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
    int lowbit(int x) {return x & -x;}
    
    int n1, n2, m;
    int h[N], e[N], ne[N], idx;
    int match[N];
    bool st[N];
    
    void add(int x, int y)
    {
    	e[idx] = y;
    	ne[idx] = h[x];
    	h[x] = idx ++ ;
    }
    
    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 main()
    {
    	cin >> n1 >> n2 >> m;
    	memset(h, -1, sizeof h);
    	for(int i = 0; i < m; i ++ ){
    		int a, b;
    		cin >> a >> b;
    		add(a, b);
    	}
    	
    	int res = 0;
    	for(int i = 1; i <= n1; i ++ ){
    		memset(st, false, sizeof st);
    		if(find(i)) res ++ ;
    	}
    	
    	cout << res << endl;
    
    	return 0;
    }
    
    
    
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
  • 相关阅读:
    PIR人体感应AC系列感应器投光灯人体感应开关等应用定制方案
    C语言之:函数的声明和定义必备练习题
    Android Material Design之MaterialToolbar(三)
    群晖DS218+部署PostgreSQL(docker)
    在WIN7下特定图片SystemParametersInfo失败,但是GetLastError()返回0
    表白墙/留言墙 —— 中级SpringBoot项目,MyBatis技术栈MySQL数据库开发,练手项目前后端开发(带完整源码) 全方位全步骤手把手教学
    MySQL---函数的类型和演示
    数据可视化时代,为智慧城市建设添彩_光点科技
    项目管理平台—基于Jira平台—工作流
    大学生竞赛指南 互联网+
  • 原文地址:https://blog.csdn.net/qq_52354698/article/details/126898529