今天教图论

二分图匹配（匈牙利算法）

基于增广路的算法：

for(i~n)
    for(j~n)
        if(j未匹配||和j匹配的能匹配其它数)
            i和j匹配

还有几个公式：

最大匹配数=最小点覆盖数
最大匹配数=n-最小独立集数

欧拉图

应该都会了，对吧

2—sat

背景：

有n对，每对2人，只能到场1个，不同对之间的某些人可能有矛盾，问如何安排使n个人到场

建边

若{A1，B1} {A2，B2}两队，A1和B2有矛盾，那么把{A1，B1}和{A2，B2}建边

边表示选了一个端点就必须选另一个

然后找出必选点后缩点再跑SCC就行了