这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有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)就会出错)
代码:
Category Archives: 图论
斯坦纳树相关
1.复杂度 O(n*3^k+cE*2^k)
上下界网络流的一些理解
周源论文中的二分法求解虽用途广,但效率不高,容易被卡时间,所以非二分的扩流法和缩流法比较好
注意点:设下界为low,上界为high,残量网络中该边残余容量c,则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
(1)加弧
(2)添加附加源汇ss、tt。求出是否存在可行流。
(3)现在已经有了可行流,去掉
2.有源汇上下界最小流
(1)和最大流一样构造附加网络(但不添加
(2)求ss到tt的最大流ans1
(3)加
(4)如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇),则有解,且
这个方法无bug,但我还没完全理解
还有一个有bug的方法:和求解最大流基本一样,只是最后一步是从t到s求最大流,也就是缩流,但是存在bug:可能出现缩流的量比可行流还大,也就是最终最小流为负,其实这种情况意味着原网络中间出现环流,也就是源点s不必产生流量也能符合要求,此时最小流为0
上下界网络流专题
各种流的一句话总结,相当经典:http://blog.csdn.net/pouy94/article/details/6628521
zoj 2314 Reactor Cooling
无源汇可行流
欧拉回路 && 特殊图下的哈密顿专题
写了标题,防止懒惰,补上题解
哈密顿回路存在性判断的一些充分条件
(已会)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
算法结束
求最大点独立集的一个可行解:所有点去掉最小点覆盖集的点
二分图(最大/多重)匹配专题
hdoj1068 最大独立集
小试一下写的模板
双连通专题
前段时间空间和域名超期了,刷的几个专题都没记录,忘了一大半。。
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跑的。。囧~)
网络流之最小费用最大流
每次找费用最小的增广路即可。
网络流专题
把原来讲座的网络流专题补上。。
网络流题集:风神博客
不错的博客:http://yangzhang91.com/%E7%BD%91%E7%BB%9C%E6%B5%81%E4%B8%93%E8%BE%91.htm