二分图进阶指南

前置知识：匈牙利算法，zkw费用流，Floyd传递闭包

基本概念

二分图：

指顶点可以分成两个互斥的独立集\(U\)和\(V\)的无向图，也就是在任两个同在\(U\)或\(V\)的顶点间没有边。

一般为了方便表示，我们将点集分为左右2个部分。

匹配：

边集\(E\)，其中没有任意2条边有相同的顶点

点覆盖：

点集\(V\)，使整张图中的每一条边都至少有一个顶点在\(V\)中

链：

点集\(V\)，其中任意2个点\(x\)和\(y\)，满足\(x\)可到达\(y\)或\(y\)可到达\(x\)

反链：

点集\(V\)，其中任意2个点\(x\)和\(y\)，满足\(x\)不可到达\(y\)且\(y\)不可到达\(x\)

独立集：

点集\(V\)，其中任意2个点\(x\)和\(y\)，没有边直接相连

链覆盖：

选出若干条链，使整张图的每个点都在链上

总结

问题	答案	输出方案
最大匹配	\(ans\)	\(link\)数组
最小点覆盖	\(ans\)（\(König\)）	打标记，左没有右有
最大独立集	\(n-ans\)	打标记，左有右没有
最长反链	传递闭包，\(n-ans\)	新图的最大独立集
DAG不相交链覆盖	\(n-ans\)	\(dfs\)输出结果
DAG相交链覆盖	传递闭包，\(n-ans\)	\(dfs\)输出结果
DAG最大独立集	\(n-ans\)（\(Dilworth\)）	非匹配点集
DAG最长反链	传递闭包，\(n-ans\)	非匹配点集

通过传递闭包，我们在所有联通的点之间连边，可以做到：

独立集\(\longrightarrow\)最长反链
不相交链覆盖\(\longrightarrow\)相交链覆盖

匹配

匈牙利算法：

枚举左边的点，寻找以他为起点的增广路（未匹配边——匹配边——…...——未匹配边）。

若存在这样的路径，图中的最大匹配数便加一。

若边带权，使用zkw费用流解决。

若点带权，拆点后使用zkw费用流解决。

二分图中的\(König\)定理，最小点覆盖和最大独立集

在一张跑完最大匹配的二分图上，我们从左边未匹配的点出发。沿着（未匹配边——匹配边——未匹配边——……——匹配边)的假增广路进行\(dfs\)，并将途经的点打上标记。

void dfs(int x)
{
    if(l[x])
        return;
    l[x]=1;
    for(int i=1;i<=n;++i)
        if(mp[x][i]&&!r[i])
        {
            r[i]=1;
            dfs(link[i]);
        }
}

最小点覆盖中点的个数=最大匹配(\(König\)定理)

简单的证明：

我们选出的点一定是某一条匹配边的端点，且选出的点与匹配边一一对应。

左边的非匹配点被打上了标记，不会被选出。

右边的非匹配点无法通过假增广路到达，否则就不满足已是最大匹配的条件，不会被打上标记。

匹配边上2端点的标记状态一定是相同的，每条匹配边只可能有一个端点被选出。

所以点的个数即最大匹配数。

最小点覆盖和最大独立集互为补集

简单的证明：

初始状态下所有的点都在集合中，要删除一部分点和所有与他们连接的边，使得图中没有边存在。

这个删去的点集便是最小点覆盖。

最小点覆盖=左边未标记的点+右边已标记的点

简单的证明：

假设存在没有被覆盖的边，且左端点有标记，右端点没有标记。

如果是非匹配边，那么从左端点开始\(dfs\)，他的右端点就会被标记。

如果是匹配边，由于我们从左边的非匹配点开始\(dfs\)，那么他的左端点的标记一定来源于右端点，即右端点也有标记。

所以不存在没有被覆盖的边。

最大独立集=左边已标记的点+右边未标记的点

简单的证明：

不存在一条边的2个端点都不在最小点覆盖中，每条边都至少有1个端点被覆盖。

所以剩下的点不能通过某一条边直接连接。

当点覆盖集最小的时候，剩余的点集便是最大的。

例题：HDU3335

DAG中的最小点覆盖，最大独立集

显然，我们可以将一个DAG通过拆点转换为二分图。

我们为每一个点\(u\)建立入点\(u_x\)（放在左边）和出点\(u_y\)（放在右边）。将原图中\(u\)到\(v\)的边转位\(u_y\)到\(v_x\)的边。

原图上的答案即为二分图上的答案。

但在输出方案时，有所不同。

仅当一个点在左右点都满足了对标记的要求时，才算是答案。

最小点覆盖=左边无标记且右边有标记的点

最大独立集=左边有标记且右边无标记的点

DAG中的最小链/路径覆盖

不可相交的链覆盖

最少不相交路径覆盖=原图的点数-新图的最大匹配

简单的证明：

一开始图的链覆盖为\(n\) 。

在二分图匹配中，每找到一条匹配边，则相当于有一条边覆盖原来的2个顶点，使答案减一。

所以有，最少不相交路径覆盖=原图的点数-新图的最大匹配。

可相交的链覆盖

若可从\(x\)到达\(y\)，我们便添加一条从\(x\)指向\(y\)的边。

这一过程被称为传递闭包。

for(int k=1;k<=n;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            mp[i][j]|=mp[i][k]&mp[k][j];

在原图上跑Floyd传递闭包。

如图，避免了相交的问题。原先相交的链变得不再相交，即可将这个问题转化为不可相交的链覆盖。

DAG中的\(Dilworth\)定理，最大独立集和最长反链

\(Dilworth\)定理：

DAG的最大独立集=DAG的最小不相交链覆盖

在求出最小不相交链覆盖后，图中的非匹配点即位链的终点。

非匹配点的点集即为答案的具体。

实际上，可以在每一条链中各选一个点，组成最大独立集。

观察反链和独立集的定义。

传递闭包后的图的最大独立集，任意2点之间没有连边，即任意2点不可达。

这时的最大独立集即为原图的最长反链。

输出方案的方法同上。

例题：[CTSC2008]祭祀