匈牙利算法

匈牙利算法

匈牙利算法的核心是寻找增广路径，利用增广路求二分图的最大匹配。
增广路径：若p是图g中的一条路径，在p上非匹配边和匹配边交替出现，p就是一条增广路。
例：在下面这个二分图中（1，1‘），（4，3’）是匹配边其它为非匹配边

由点3出发按照非匹配边和匹配边交替去走，路径p为3->1’->1->3’->4->4’，此时上一条走过的边为非匹配边这时候进行取反将p上的边进行取反的 *** 作（将匹配边变成非匹配边，非匹配边变成匹配边）

这时增广路径p就变成了2‘->3->1’->1->3’->4->4’->5。
匈牙利算法就是通过不断寻找增广路来获得一个二分图的最大匹配。
模板例题：
https://www.acwing.com/problem/content/375/
给定一个 N 行 M 列的棋盘，已知某些格子禁止放置。

问棋盘上最多能放多少个不能互相攻击的車。

車放在格子里，攻击范围与中国象棋的“車”一致。

输入格式
第一行包含三个整数 N,M,T，其中 T 表示禁止放置的格子的数量。

接下来 T 行每行包含两个整数 x 和 y，表示位于第 x 行第 y 列的格子禁止放置，行列数从 1 开始。

输出格式
输出一个整数，表示结果。

数据范围
1≤N,M≤200
输入样例：
8 8 0
输出样例：
8

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
int n, m, t, l[205], sum = 0;
bool a[205][205], used[205];
bool find(int x)//匈牙利算法核心代码
{
    for (int i = 1; i <= m; i++)//遍历与第x行匹配的列
    {
        if (!a[x][i] && !used[i])//判断第x行和第i列是否可以放置棋子
        {
            used[i] = true;//标记x初步判断可以匹配的点
            if (!l[i] || as(l[i]))//如果第i列还没有行跟它匹配或之前跟它匹配过的行可以与其他另外的还未匹配的列匹配那么就让第x行与第i列匹配表示这里已经放过了一个棋子
            {
                l[i] = x;
                return true;//（x，i）能够放置棋子返回true
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m >> t;
    while (t--)
    {
        int x, y;
        cin >> x >> y;
        a[x][y] = true;
    }
    for (int i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (find(i))//第i行找到了可以放置棋子的位置总共放置的棋子数就加1
            sum++;
    }
    cout << sum << endl;
    return 0;
}