Loj模板   之前学习了EK算法以及Dinic算法,它们所处理的都是有源有汇且只有上界的网络。此问题则要求流量在上界与下界之间,并且无源无汇,判断是否可行。   注意点:(1)这相当于一个循环流,对于每一个点,流入量都等于流...
阅读(20) 评论(0)
题目描述   打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现,这个打字机是这样工作的:   ·输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。   ·按一下印有'B'...
阅读(13) 评论(0)
poj 1236一个简单栗子🤭   给定一个有向图,如果一个点有了一个软件,它能到达的所有点都可以使用这个软件。ask1:问你至少需要给多少个学校配备软件,使所有的学校都可以使用到软件;ask2:问你最少需要建立多少条联系,使得你...
阅读(19) 评论(0)
题意:先给定一张无向连通图,每次有一个询问,让你求新建一条边(x,y)之后图中还有多少条割边。   如果你是打算每次重新跑一边tarjan的话,先善良的告诉你,N的范围是1e5,Q是1000。那么就另想招吧。有没有想到缩点呢?我们对...
阅读(13) 评论(0)
一张无向图中不存在割边,则称它为边双连通图。无向图的极大边双连通子图称为图的边双连通分量,即e—DCC。   一张无向连通图是边双连通图,当且仅当任意一条边都至少包含在一个简单环里。道理很显然,就不证明了。   怎么求e—DCC呢?...
阅读(20) 评论(0)
上回介绍了EP算法,这次来学一个效率更高的算法。我们在做EP算法的时候,每次bfs最多遍历了整个残量网络,但是只找到了一条增广路。所以有可以优化的地方。Dinic算法基于分层图,我们先bfs找到一个合法的有向无环图(图中所有边都有残...
阅读(35) 评论(0)