题面 传送门：洛谷 Solution 先跟我大声念： $\huge poi!$ . 然后开始干正事。 首先，我们先把题目中的点分为两类：去除这个点能把图分为几个部分的，去除这个点不影响整个图的连通性的。 如下图： 点上的数字表示这个点的搜索序。 我们称这些对连通性有影响的点为割点。 先假设我们能求出这些点以及其出去后把图分为几块之后那几块分别的大小。 是不是发现了什么？ 对于非割点，答案...

题面 传送门：洛谷 Solution 这题显然要先把缩点做了。 然后我们就可以考虑如何处理走反向边的问题。 像我这样的蒟蒻，当然是使用搜索，带记忆化的那种（滑稽）。 考虑设$f(i,j)$表示到达第i个点，还能走j次反向边，所能到达的最多的点的数量。 转移可以表示为： 如果x能到达1所在的强连通分量或max出来的值不为0，说明当前状态可行，否则不可行。 然后用记忆化搜索表达出来就OK了 ...

题面 传送门：洛谷 Solution 前排提示，本蒟蒻做法既奇葩又麻烦 我们先可以把题目转换一下。 可以把一头牛喜欢另外一头牛理解为另外一头牛被一头牛喜欢。 我们把被喜欢的关系建边，即B被A喜欢，从B向A连一条有向边。 显然，一个点若能到达其他所有节点，它就是题目中的明星牛。 接下来，我们可以考虑一个类似于DP的做法。 即一个点能访问到的点，等同于它的儿子们访问的到的点加上它自己。 显然，...

题面 传送门:洛谷 Solution 这道题,需要一个小技巧了解决。 我相信很多像我这样接蒟蒻，看到这道题，不禁兴奋起来：“这道题是裸的割边，我会做！！！” 然后兴冲冲的打了个DINIC，交一发，80分。 所以说我们有时候还是太naive。 重新读题，会发现这题割的不是边，是点。这样还能80分，数据真水 所以说，我们需要一个割边转割点的小技巧。 我们可以考虑“拆点”，即把一个点拆成两个点，...

题面 传送门:洛谷 Solution 这题的思想很巧妙. 首先,我们可以考虑一下最暴力的做法,对每个时刻的所有点都求一遍单元最短路 因为最多只有200个时刻,时间复杂度为$O(n^3log(n+m)))$ (堆优化的迪杰斯特拉) 显然对于$n=200$,并过不了 我们可有进一步分析 这一题,我们堆优化的迪杰斯特拉慢在每加入一个点,我们每一次都得对全图彻彻底底做一轮松弛 那换个角度考虑,如果...

传送门：洛谷 Solution 网络流 先引用一句真理:网络流最重要的就是建模 今天这道题让我深有体会 首先,观察数据范围,n=100,一般这种100-1000的图论题,很有可能是网络流. 那就直接从网络流的角度入手 考虑这样建模 建模要点如下: 1.建权值为1的边,保证每个食物和水仅用一次 2.没了 对以上的图求一个最大流,那不就是我们想要的最大的匹配数吗? 看起来是不是很OjbK? ...