匈牙利算法

参拜大佬%%%

二分图

定义

  严格的定义请参加百度百科什么的.这里简单讲一下我的理解.就是给你一个图,有n个点.你可以按照边的关系,将这n个点分成两部分,而且这两部分之间有边相连.但是每一部分里面的点互不相连.
  如图1,左右两部分的点随意相连,但是每部分里的每一个点互不相连.

匹配

  首先是极大匹配(Maximal Matching),是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
  而最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
  如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
  求二分图匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm).
  当然本蒟蒻还没有学最大流

匈牙利算法

  我们来看图二,可以知道了这个二分图各点之间的联系.那么该算法如何实现最大匹配呢.

  根据字典序,显然易见,我们可以知道,A->E.
  随后,我们看B点,它要连E,但是E被占用了,我们该怎么办?我们把A->E之间的边暂时去掉,变成黄色,然后让B->E链接,但是A不能没有,于是这里从A再走,E不行,但是有个F.所以A->F.


  于是C->G也按此法加上,轮到D,我们发现G已经被连了.怎么办?将C->G的边暂时去掉.再从C走,看是否可以找别的边.但是我们发现,C只有到G的一条边.所以C->G保留,D只能孤立一人,我们无能为力.

核心代码

bool find(int x)
{
    for (int i = 1; i <= ny; i++)
        if (!used[i] && m[x][i]) {    //used[]指的是,这个点是否被处理过.m[][]是指两者之间是否相连
            used[i] = 1;
            if (!y[i] || find(y[i]))  //如果这个点没有被链接,或者可以调整
                return y[i] = x;
        }
    return 0;
}

完整代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<string>
#include<math.h>
#include<map>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
#define maxn 10000
using namespace std;

typedef long long ll;
int m[maxn][maxn], used[maxn],y[maxn],nx, ny;
bool find(int x)
{
    for (int i = 1; i <= ny; i++)
        if (!used[i] && m[x][i]) {
            used[i] = 1;
            if (!y[i] || find(y[i]))
                return y[i] = x;
        }
    return 0;
}
int main()
{
    int ans = 0,d;
    cin >> nx >> ny>>d;
    for (int i = 0; i < d; i++) {
        int x, y;
        cin >> x >> y;
        m[x][y] = 1;
    }
    for (int i = 1; i <= nx; i++) {
        memset(used, 0, sizeof(used));
        if (find(i))
            ans++;
    }
    for (int i = 1; i <= ny; i++)
        cout << y[i] << ':' << i << endl;
    cout << ans << endl;
    return 0;
}