国庆集训Day2笔记

图论

最短路

算法

floyd:(f_{k,i,j})为只使用(1-k)中的点的最短路,(f_{k+1,i,j}=max(f_{k+1,i,j},f_{k,i,p}+f_{k,p,j}))(无负环)

dijkstra:(边权非负时正确)每次在没有选择过的点中,选择距离最小的(u),并更新所有相邻点的距离

Bellman-Ford:随机选择一个节点更新相邻点(边权可为负)

CF295B(solved)

倒序加点+floyd

NOI2007社交网络

最短路计数模板题

可以在floyd的同时维护最短路条数

jzoj6354

[w->frac{1}{1-w}->frac{w-1}{w}->w ]

分层图最短路

连通分量

算法

强连通分量(有向图):有向图的某一个子图,使得子图内任意两点可互达(使用Tarjan求解)

双连通分量(无向图):
(1)点双连通分量:对某个子图,任意删去一个点后子图仍联通。
注意一个点可以属于多个点双连通分量中

(2)边双连通分量:对某个子图,任意删去一条边后子图仍联通。

圆方树:圆点为原图中的点,方点为每一个点双连通分量,若某个点属于某个点双则连边,图中一定不存在环

WF2011H

按照割点个数分类讨论

UOJ Goodbye Jiawu B

树:(m=n-1)且联通

割点不能删,暴力计算边数

BJOI2013 压力

圆方树上的((u,v))两点路径上的圆点是必须要经过的点,同一个点双内的其他点不一定要经过(点双定义)

树上差分统计答案

差分约束系统

定义

给出(n)个非负变量和(m)个不等式(x_i-x_jgeq k),求是否有可行解且最小化(sum x_i)

求解

(x_igeq x_j+k->x_j连向x_i且权为k)

图中正环则无解,否则建立超级源求最长路

小于等于同理,但是需要求的是最短路且为最大解

POI2012 Festival

(x_i=x_j+1)等价于(x_ileq x_j+1且x_igeq x_j+1(x_jleq x_i-1))

(x_ileq x_j)

求SCC并重构图

SCOI2011 糖果

不使用SPFA时,SCC缩点,由于不能存在正环故不存在(1)边,也就是所有点都一样

2-SAT

定义

(x_i op x_j=1),求可行解

解法

(x_{i})拆成(x_{i0},x_{i1}),若(x_{a}=p)(x_b=q),则(x_{ap})(x_{bq})连边(对称性)

SCC缩点后每个SCC内的点要么都选要么都不选,得到一个DAG

无解:(x_{i0})(x_{i1})在同一个SCC中

构造方案:按照逆拓扑序考虑,每次找到一个可选点之后标记所有的不可选点

JSOI2010 满汉全席(solved)

模板

NOI2017 游戏(solved)

枚举?的取值,转化成2-SAT

Other

定义

独立集:(Sin V)使得(forall u,vin S,(u,v) otin E)

团: (Sin V)使得(forall u,vin S,(u,v)in E)

点覆盖: (Sin V)使得(forall (u,v)in E,uin S or vin S)

支配集:(vin V)(S),(exists uin S,s.t. (u,v)in E)

(以上均为NPC问题)

欧拉路径:经过每一条边的路径(奇点个数为0或2)

欧拉回路:欧拉路径为环(奇点个数为0)

POI2011 Party

POI2011 Conspriracy

POI2011 Garbage

AtCoder杂题

ARC102E

容斥

ARC101D

二分答案

中位数(geq x)等价于将(geq x)的数看成(1),剩下的数看成(-1)后区间和(geq 0)

预处理前缀和后BIT即可

ARC101E(solved)

容斥,没有不经过的->枚举不经过的边的子集,其它随意,则每一对点要求在同一个连通块内匹配。对一个大小为(x)的连通块,方案数有((x-1)(x-3)···3·1=(x-1)!!)

优化:(f[u][s][c])表示(u)子树中,(u)所在的块中未匹配的点数为(s),已经有(c)个连通块的匹配方案数,枚举与父亲是否切开进行转移。注意最后容斥系数是((-1)^c),那么直接记录(c)的奇偶性或者将容斥系数带入即可

ARC101F

机器人之间互相独立,且一个机器人的运动范围可以看成([l_i,r_i])

((l_i,r_i))放在二维平面上,所有操作可以看成一条折线,在折线下方的点则往右边掉,在上方则往左边掉。枚举L同时观察R会向上走多少,只有在某个点发生转折时才会引起方案的变化,且之前发生转折比这一次低的都可以转移到这里,前缀和优化即可

ARC099D(solved)

大力打表猜结论

ARC099E

考虑原图的补图,此时的边对应着两个点不能被划分到同一个团里面

对每个连通块判断其是否为二分图,非二分图则无解;若全是二分图则背包判断最优解

ARC096E(solved)

容斥,(S)表示出现次数不超过(1)次的数,枚举(|S|=k),则(ans=sum_{k=0}^ndbinom{n}{k}(-1)^kf(k))(f(k))表示(1-k)出现至多1次的方案数

(f(i)=sum_{j=0}^i 2^{2^{n-i}}2^{(n-i)j}g(i,j))
其中(j)是包含(1-i)中的数的集合个数,(2^{2^{n-i}})表示在这(j)个集合之外的,包含剩下(n-i)个元素的集合数为(2^{n-i}),然后它们都可以出现或者不出现,方案数为(2^{2^{n-i}})(2^{(n-i)j})表示包含(1-i)的这(j)个集合中,剩下的元素一共有(2^{n-i})种可能的出现情况,然后又有(j)个这样的集合,方案数就是(2^{(n-i)j}).(g(i,j))表示(i)个元素放在(j)个集合中,且每个元素出现至多一次的方案数

求解(g(i,j)):注意到(g(i,j))(egin{Bmatrix}i\j end{Bmatrix})的定义类似,我们考虑将元素看成球,将集合看成盒子,那么(g(i,j))等价于补充一个新盒子和一个新球,并且最后将新球所在的集合删去得到。所以(g(i,j)=egin{Bmatrix} i+1\j+1 end{Bmatrix}),仿照第二类斯特林数进行递推即可

原文地址:https://www.cnblogs.com/encodetalker/p/11618016.html