Java教程

二分图最大匹配模板(匈牙利算法)

本文主要是介绍二分图最大匹配模板(匈牙利算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <bits/stdc++.h>
using namespace std;

int n,m,e;
int G[501][501],match[501],vis[501];
int x,y;
int ans;

int dfs(int now)
{
    for (int i = 1; i <= m; i++)
    {
        if(G[now][i] && !vis[i])
        {
            vis[i] = 1;//被匹配了或者此点没有方案
            if(!match[i] || dfs(match[i]))//可以匹配,或者以匹配的点有其他方案
            {
                match[i] = now;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++)
    {
        cin >> x >> y;
        if( x <= n && y <= m )G[x][y] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        ans += dfs(i);
        memset(vis,0,sizeof(vis));
    }
    cout << ans;
    return 0;
}

本质是贪心

流程:

        一个一个匹配

        遇到匹配过的,取搜那个匹配的点有没有其他的方案,有就结束,没有当前就换点,没点可换,就结束

这篇关于二分图最大匹配模板(匈牙利算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!