一般图的最大团

//自己第一次写的模板没用dp,怎么搞都一直2s多。。用下面的模板则可以达到700ms左右。orz。。自己加了些注释,其实很好理解
n:标号1~n,n个点
map[][]:图的邻接阵
dp[i]:表示G({i……n},ei)这个子图的最大团点数。
x[]:当前最大团
path[]:最后的最大团方案
adj[i]:与i邻接且标号比i大的顶点。
ans:算法进行到当前时刻已知的最大团点数。
注意:求出的是字典序最小的最大团。(要使字典序最大,则当=的时候不剪枝)
为什么倒着枚举:求解dp[i]的时候dp[i+1……n]都已求出
附加:算法过程中依次求出了G({n},e1)、G({n-1,n},e2)、G({n-3……n},e3)………                      G({1……n},en)这些子图的最大团。
延伸:如果要在算法过程中依次求出G({n},e1)、G({n-1,n},e2)、G({n-3……n},e3)                    ……G({1……n},en)这些子图的最大团,
那么只要:
(1)从小到大枚举每个点
(2)adj表示与i邻接且标号<i的点集(从大到小排)
(3)dp[i]表示G({1……i},ei)这个子图的最大团点数

稳定婚姻问题

设男生有n个,女生有m个。
(1)n=m,一定有解
(2)n!=m,少的那一方能完全匹配
(3)男生求婚,则最终答案是保证每个男生追到尽量好的女生,反之亦然
(4)求婚一方在算法进行过程中对象质量会越来越差,被动一方则相反
(5)求婚一方在订婚后可能变成单身(失配),但是被动一方一旦被求过婚,它就一定不可能单身了。

关于二分图一些概念的记录

最大匹配其实就是最大边独立集
最小点覆盖集=最大边独立集
最小边覆盖集=最大点独立集
求最小点覆盖集的一个可行解:
法一:见matrix67对二分图最大匹配的König定理的证明
法二:
算法实现步骤:
1. 做最大匹配,没有匹配的空闲点∈S
2. 如果u∈S那么u的邻点必然属于T
3. 如果一对匹配的点中有一个属于T那么另外一个属于S
4. 还不能确定的,把左子图的放入S,右子图放入T
算法结束
求最大点独立集的一个可行解:所有点去掉最小点覆盖集的点