zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

上下界网络流的一些理解

周源论文中的二分法求解虽用途广,但效率不高,容易被卡时间,所以非二分的扩流法和缩流法比较好
注意点:设下界为low,上界为high,残量网络中该边残余容量c,则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
(1)加弧,转变成无源汇可行流问题
(2)添加附加源汇ss、tt。求出是否存在可行流。
(3)现在已经有了可行流,去掉。从s到t求最大流,(网上说要去掉附加源汇ss,tt,其实我感觉不用去,因为ss和tt间没边,所以必要弧不可能退流,个人理解,正确性有待检验)
2.有源汇上下界最小流
(1)和最大流一样构造附加网络(但不添加
(2)求ss到tt的最大流ans1
(3)加,求ss到tt的最大流ans2
(4)如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇),则有解,且的流量就是最小流,否则无解
这个方法无bug,但我还没完全理解
还有一个有bug的方法:和求解最大流基本一样,只是最后一步是从t到s求最大流,也就是缩流,但是存在bug:可能出现缩流的量比可行流还大,也就是最终最小流为负,其实这种情况意味着原网络中间出现环流,也就是源点s不必产生流量也能符合要求,此时最小流为0

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

(已会)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条件强一些而已

一般图的最大团

//自己第一次写的模板没用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
算法结束
求最大点独立集的一个可行解:所有点去掉最小点覆盖集的点

双连通专题

前段时间空间和域名超期了,刷的几个专题都没记录,忘了一大半。。
hdoj:
2242考研路茫茫——空调教室 双联通缩点+树形DP
2460Network 边双连通
3849By Recognizing These Guys, We Find Social Networks Useful 双连通求桥
3896Greatest TC 双连通
4005 The war 边双连通
3394Railway 双连通求块

强连通专题

按着风神大大的博客切啊切~
提示在每道题后面,选中即可显示
HDOJ
hdoj1269 迷宫城堡 判断是否是一个强连通★
hdoj2767Proving Equivalences 至少加几条边让整个图变成强连通★
hdoj3836 Equivalent Sets 至少加几条边让整个图变成强连通★
hdoj1827 Summer Holiday 传递的最小费用★★
hdoj3072 Intelligence System 传递的最小费用★★
hdoj3861The King’s Problem 强连通+二分匹配★★

这题必须好好记下,题意木有读懂,orz。。
题意:在有向图G中,相互可达的两个点必须划分在一个区,并且一个区里的任意两个点,至少存在一条单向路径(不经过其他区的点)。问原图最少需要划分成几个区。
思路:首先相互可达的点必须在一个区,那么强连通缩点,这样形成了一个DAG森林。问题转化为:给定一个DAG森林,最少用几条路径可以覆盖所有点,每个点只能属于一条路径。其实就是求DAG森林的最小路径覆盖,拆点转化成二分图,最小路径覆盖=原图顶点-最大匹配
通过这道题顺便学了最小路径覆盖,然后整理了一些覆盖集、独立集之间的关系,爽。
代码(匹配还没学,,用sap跑的。。囧~)