• 欢迎光临~

Blue Book 上的图论T(未完成)

开发技术 开发技术 2022-10-28 次浏览

Sorting It All Out:

对于可以得到绝对顺序的图,拓扑排序可以直接确定顺序
如果拓扑排序没能遍历所有的点,就说明存在一个环。
set也可以用count,我为什么才知道

Sightseeing trip:(无向图的最小环问题):

考虑一个图中的最小环u->v->k->u,如果我们随意去掉其中一条边u->v
那么剩下的v->k->u一定是图中u->v建的最短路径
在Floyed算法枚举k的时候,已经得到了前k-1个点的最短路径,这k-1个点不包括k,并且他们的最短路径中也不包括k点
由对称性可知,这样做并不会影响结果

走廊泼水节;(https://www.acwing.com/problem/content/348/)

又是熟悉的感觉?有一个题是完全图最短路,开始边权相同,后来有修改,修改只涉及了最多6000个点,就把修改的拿出来
好像是多校里的某个T4->欢乐豆,这种取出某些点单独最短路的套路可以应用到[最短路问题V3]
为了保证(x, y)一定在最小生成树中,就必须让(x, y)是连接集合Sx与Sy的权值最小的边,因此(u, v)的权值应该定为w(x, y)+1
求增加的边的权值,从原有的边里找

Picnic Planning:(https://www.acwing.com/problem/content/349/)

书看了一半,以为拆出来连通块之后问题就完美解决,然后被后半部分吓到了
鹤完文字版就鹤code
没有作者的高级题意转化还真不容易想到最小生成树,关于映射也有一点细节
口胡很容易但是对鹤就不太友好。。
Star way to heven 好像也是一道用prim跑最小生成树的题,很少用prim还是很不熟练
忽然发现也不是必须用prim。。

程序员灯塔
转载请注明原文链接:Blue Book 上的图论T(未完成)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com