什么是最小树形图 最小树形图就是给定一个$n$个点的有向图，我们钦定一个根，现在要找$n-1$条边，在根能到达其他所有点的前提条件下，使得$n-1$条边的总长度尽可能小。 怎么找最小树形图 这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然，还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了，并学不会 图出自这里 上面这张图很好的诠释了朱刘算法的主要内...

题面 UVA10972 RevolC FaeLoN Solution 这题就比较牛皮。 我们先来考虑一下图联通的话怎么做。显然，我们可以先把图按边双缩点，边双内部是肯定不用加任何一条有向边就能改成强连通分量的（易证）。 缩完点之后，图一定会变成一颗树。接下来我们依旧可以像这道题那样贪心。我们数一下广义叶子数有多少，要加的边的个数一定为$sum/2$（向上取整）。 连边方式如图所示： 接下来...

题面 UVA610 Street Directions Solution 先来解释一下题面意思：我们现在有一个联通的无向图，我们要把整个图改造为有向图，在保证强连通的情况下使得双向边尽可能少。 我们不妨思考一下：如果一条双向边被我们改造为了单向边，会导致某一个方向上的断开。因此，我们先对原图做边双缩点，桥边是不可能被改造为单向边的（因为改造后直接导致边双间不能互相联通）。 除了桥边之外，其他...

题面 P2860 [USACO06JAN]冗余路径Redundant Paths Solution 首先，我们可以发现题目要求每一个点到其他所有点的路径不只有一条，这本质上就是要我们把这个图所有的桥都消除掉。 要消除掉桥，首先必须要把边双先缩起来。缩边双很简单：和求强连通分量一模一样，唯一要注意的是我们要多记录一个$fa$，防止我们求$low$的时候直接把$fa$算进来。 求完边双之后，我们...

题面 P3225 [HNOI2012]矿场搭建 Solution 这题比较妙。 首先，根据常识，如果一个点爆了，当且仅当它是割点的时候才会影响整个图的连通性。 因此，我们考虑把这道题往点双那方面想。 接下来我们思考这个问题：对于一个点双，我们什么时候需要在它这里面放置逃生通道： 如果与它相连的点双块只有一个：如果爆的是割点，则必须在当前块中的任意点建一个通道；如果爆的是普通点，则当前块则可...

题面 P4606 [SDOI2018]战略游戏 Solution 圆方树上圆方果， 圆方树下你和我。 圆方树前建虚树， 欢乐多又多。 好吧，我们来说正题。 这题就比较强。根据常识，如果我们爆掉的点能影响这个图的连通性，那么，这个点一定是割点。 因此，我们要先对原图做Tarjan求点双。接下来，我们考虑用圆方树来解决一个问题。 我们先考虑暴力怎么做，我们先对原图求出圆方树。 接下来，我们...

题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题，我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法：对于每只doge，我们都暴力地去建它连向它能跳到的点的边，边权为跳的次数。然后直接求一遍单元最短路即可。 很显然，这玩意的边的数量是$O(n^2)$的，求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的，但是我们会从中...

什么是边双？ 双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用Tarjan算法。——百度百科 用人话来说，就是在无向图上以边为关键字，对原图缩点 为什么要学边双 与强连通分量类似，我们可以求...

题面 蒟蒻博客：QAQ Solution 这是一道神题 首先，我们不妨想一下K=0，即求最短路方案数的部分分。 我们很容易可以想到一个做法，就是魔改迪杰斯特拉做法： 一个点可以更新到达其他点的距离，那个点的方案数就是这个点的方案数；如果一个点所更新出来的距离和之前的相等，那个点的方案数加等当前点的方案数。 用式子可以表现为： $$f[i]=f[i] (dis[j]>dis[i]+x)...

题面 传送门:洛咕 Solution 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到2的n次方，那么这两个点可以用1的时间相互到达。 也就是说，我们把距离能为2的n次方的点对用边权为1的边连上，再做一次最短路径，就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。...