哈密顿回路存在性判断的一些充分条件

(已会)1.Dirac定理:无向图共n个顶点,每个顶点的度数均>=ceil(n/2),则该图一定含有哈密顿回路

(3的充分条件)

2.设G是含有n个顶点的无向简单图,如果G的每一对顶点度数之和>=n-1,则G一定存在哈密顿路

(已会)3.设G是含有n个顶点的无向简单图,如果G的每一对顶点度数之和>=n,则G一定存在哈密顿回路(Dirac定理的必要条件)

(已会)4.竞赛图一定有哈密顿路

5.竞赛图含有哈密顿回路当且仅当该竞赛图强连通

1.3的解决方法一样的,因为1和3本质相同,1比3条件强一些而已

hdoj4565 So Easy!

矩阵题,2013长沙邀请赛的题,但是貌似oj没有题目重现的比赛,没做到,结果长沙online居然出现了一道同一类型的题,,直接哭瞎了。。
需要用到无理数共轭的概念
具体题解:http://blog.csdn.net/xh_reventon/article/details/9970259
想到共轭就比较好做了。

一般图的最大团

//自己第一次写的模板没用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)这个子图的最大团点数

2013 ACM/ICPC Asia Regional Chengdu Online–1010

hdoj4737 A Bit Fun
题意:给出n,m,然后给你n个正整数(n<=10^5),设f(i,j)=ai|ai+1|ai+2|……|aj,(i<=j),问有多少不同的f(i,j)<m.
总体思路:假如有一段连续的数[ai……aj aj+1],由于位或运算会使得结果越来越大,所以f(i,j)<f(i,j+1),那么可以很快得到二分的算法:一次枚举第i个数,二分[i,n]这一段数,找到最大的t,满足f(i,t)<m.
但是问题是n是10^5,每次暴力计算f(i,j)都是O(n)的(这样做就没有二分),这样复杂度是O(n^2)的,怎么降低复杂度呢(貌似这题数据比较水,比赛的时候很多大一队员是用暴力水过的,,==!)。
关键在于要常数时间计算ai|ai+1|ai+2|……|aj。可以这样做,a[i][k]表示前i个数对应第k位(把数分解成二进制)上“1”的个数之和,显然如果a[i-1][k]<a[j][k],那么说明[ai,aj]这段连续的数中至少存在一个数它的第k位是“1”,那么这段数位或起来,结果的二进制第k位一定是“1”,反之亦然。这样枚举结果的每一位分别是1还是0即可,一个数最多30位,自然是常数。

稳定婚姻问题

设男生有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
算法结束
求最大点独立集的一个可行解:所有点去掉最小点覆盖集的点

近期比赛待做的题

2013 ACM/ICPC Asia Regional Online —— Warmup
hdoj4714 Tree2cycle
hdoj4712 Hamming Distance
HDU Single Congtest 0905 (For Old ACMer)
zoj1301 The New Villa
HDU Single Congtest 0907 (For Old ACMer)
zoj1063 Space Station Shielding
zoj1066 Square Ice
zoj1197 Sorting Slides
HDU Team Congtest 0910 (For Old ACMer)
zoj1462 Team Them Up!
zoj1391 Horizontally Visible Segments