💡
二分图最大匹配 最小点覆盖,最大独立集 总点数 最小点覆盖。
先对原图跑最大匹配,在残量网络上跑 tarjan 求强连通分量。
可行边:该边为原图上的匹配边或两点属于相同的强连通分量。
必经边:该边为原图上的匹配边且两点属于不同的强连通分量。
可行点:所有可行边的所有端点。
必经点:统计非必经点,从 走流量为 的边走到的左部点与从 走流量为 的边走到的右部点为非必经点。
定义二分图的完美匹配为匹配数量 左部点数量。
一张二分图存在完美匹配的充要条件为:对于左部点的任意一个子集,其连到的右部点数量都 这个子集的大小。