二分图最大匹配

• 匈牙利算法

本质上是一个调整策略的方法，有点类似反悔贪心。

首先让可以匹配的点直接匹配（不必顾及后面的点），之后到了某个点进行匹配时，如果该点可以匹配直接匹配，否则从该点所连的对应点开始，找到它的上一个匹配点，让他尝试着更换一个匹配，如果成功更换匹配就更新当前匹配，否则匹配失败，这样最后总会得到一个最大匹配。

具体实现so ez， 设置一个vis标记当前对应点是否在更新的交替路中，设置Match作为对面的点的匹配，dfs即可。

struct Match {
    int n;
    vector<vector<int>> e;
    vector<int> match, vis;

    Match(int n) : vis(n + 1), n(n) {
        e.resize(n + 1);
        match.assign(n + 1, -1);
    } 

    bool dfs(int x) {
        for (auto v : e[x]) {
            if (!vis[v]) {
                vis[v] = 1;
                if (match[v] == -1 || dfs(match[v])) {
                    match[v] = x;
                    return true;
                }
            }
        }
        return false;
    }

    void add(int u, int v) {
        e[u].push_back(v);
    }

    bool find(int x) {
        vis.assign(n + 1, 0);
        return dfs(x);
    }

    int maxMatch() {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += dfs(i);
        }
        return res;
    }
};

• 转化成网络流

从源点向左侧集合链接边权为1的边，右侧集合向T链接1的边，最大流即是最大匹配