【图论】图的匹配问题

图的匹配问题（二分图（最大）匹配）

概念

• 边集中边数最大为最大匹配，边权和最大的为最大权匹配 。
• 完全匹配，也叫做完备匹配，即某个匹配中，每个顶点都和某条边相关联。
• 点覆盖集 ：无向图的一个点集，使得该图中的所有边至少有一个端点在该集合内。点数最少的点覆盖集被称为最小点覆盖集。
• 点独立集 ：无向图的一个点集，使得该集合中任意两个点之间不连通。点数最多的点被称为最大点独立集。
• 二分图：可以将点分成两个集合，使得每条边的端点都不在一个集合里，两个集合的点称左部点和右部点，没有节点个数为奇数的环

二分图匹配

二分图的最小点覆盖集大小+最大点独立集大小=图中点的个数

染色法：

vector<int> G[N];      
int n;                 //顶点数
int color[N];          //顶点的颜色 （1 or -1）
bool dfs(int u, int c) //染色法，顶点u，颜色c
{
    color[u] = c;
    for (auto v : G[u]) //遍历每个相邻点
        if (color[v] == c || (!color[v] && !dfs(v, -c)))
            return false; //如果染同样色，或染不同色失败了，说明不是二分图
    return true;
}
bool solve() //判断是否是二分图
{
    for (int i = 0; i < n; i++)      //遍历每个未被染色点
        if (!color[i] && !dfs(i, 1)) //如果染色失败
            return false;
    return true;
}

增广路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边⋯形成的路径叫交替路。整个路径两个端点都是未匹配点，这条路就是增广路。

二分图最大匹配

• 一个边集使得每条边没有公共端点

• 增广路定理：找不到增广路则当前匹配就是最大匹配，如果找得到只需要翻转增广路的匹配边和非匹配边。

匈牙利算法

• 对于左部点$u$ ，枚举所有连边，出点$v$ 若没有匹配直接匹配（找到增广路），否则让$v$ 之前的匹配左部点递归匹配右部点（每一轮递归右部点只能访问一次）找增广路，如果找到未匹配点即找到增广路，则$u$ 与$v$ 匹配，否则$u$ 失配。左部点比右部点少可以优化。复杂度$O(VE)$ 。
• linker[v]=u 就是匹配方案

int uN, vN;  //左右部点的数目，注意访问的起点是0/1
int G[N][N]; //邻接矩阵
int linker[N]; //记录匹配
bool vst[N]; 
bool dfs(int u)
{
    for (int v = 1; v <= vN; v++) //遍历右部点
        if (G[u][v] && !vst[v]) //u连v且v本轮递归没有访问过
        {
            vst[v] = true; //标记访问
            if (linker[v] == -1 || dfs(linker[v])) //如果未匹配或递归成功匹配
            {
                linker[v] = u; //标记匹配
                return true;
            }
        }
    return false;
}
int hungary()
{
    int res = 0;
    memset(linker, -1, sizeof(linker));
    for (int u = 1; u <= uN; u++) //遍历左部点
    {
        memset(vst, false, sizeof(vst));
        if (dfs(u))
            res++;
    }
    return res;
}

Dinic（网络流）

• 建超级源点$s$ ，向左部点各连一条容量为$1$ 的路
• 建超级汇点$t$ ，右部点向其各连一条容量为$1$ 的路
• 给定边，左部点向右部点连一条容量为$1$ 的路
• 注意节点总数、加边的点序号