一道hdu 2063彻底搞懂二分匹配--匈牙利算法

我会带着你远行 2022-08-10 15:48 106阅读 0赞

/*hdu 2603 简单的二分匹配--匈牙利算法
    这是个经典的二分匹配问题：
    匈牙利算法与寻找最大流算法类似基本操作
    ：
    初始时最大匹配为空
    while 找得到增广路径
        do 把增广路径加入到最大匹配中去
    增广路径有几点性质须知道：
    (1)有奇数条边。
    (2)起点在二分图的左半边，终点在右半边。
    (3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）
    (4)整条路径上没有重复的点。
    (5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。
    (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。
    (7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，
    并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。
    其实也是种模板算法，主要核心算法为：dfs函数，和solve函数可以好好理解一下，模板固然很好，但是能理解其中意思，可以收获更多的实质性东西
    最后一点需要明白一个原理：
    如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。
    可以好好理解下。
    如还有什么不明白地方或者不妥地方，请指出，本人不胜感激。
    */
    # include<iostream>
    # include<cstdio>
    # include<cstring>
    # include<cstdlib>
    # include<cmath>
    # include<algorithm>
    using namespace std;
    const int N=508;
    int map[N][N];//用一个二维数组来储存题目给出已配对的数据
    int match[N];
    bool flag[N];
    int n,m;
    bool dfs(int x)//用dfs来寻找最大的增广路径
    {
    	for(int i=1;i<=m;i++)
    	{
    		if(!flag[i]&&map[x][i])//如果原已匹配并且没有被访问
    		{
    			flag[i]=1;
    			if(match[i]==-1||dfs(match[i]))//递归思想一直寻找增广路，直至找不到为止
    			{
    				match[i]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    int solve()
    {
    	memset(match,-1,sizeof(match));
    	int ans=0;
    	for(int i=1;i<=n;i++)
    	{
    		memset(flag,0,sizeof(flag));//需注意每次都必须对flag标记数组进行初始化清空操作
    		if(dfs(i)) ans++;//ans就记录了最大匹配数
    	}
    	return ans;
    }
    int main()
    {
    	int t;
    	while(scanf("%d",&t)&&t)
    	{
    		scanf("%d%d",&n,&m);
    		memset(map,0,sizeof(map));
    		for(int i=0;i<t;i++)
    		{
    			int u,v;
    			scanf("%d%d",&u,&v);
    			map[u][v]=1;//建图操作
    		}
    		int ans=solve();
    		cout<<ans<<endl;
    	}
    	return 0;
    }