Category Archives: 图论

zoj 3761 Easy billiards dfs树

Posted on by

这题如果想到的话，写起来很简单。。
题意：无限大的二维坐标系中有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)就会出错)
代码：

上下界网络流的一些理解

Posted on by

周源论文中的二分法求解虽用途广，但效率不高，容易被卡时间，所以非二分的扩流法和缩流法比较好
注意点：设下界为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

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

Posted on by

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

一般图的最大团

Posted on by

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

稳定婚姻问题

Posted on by

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

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

Posted on by

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

双连通专题

Posted on by

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

强连通专题

Posted on by

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

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