妙啊！！
无定根的最小树形图，没想出来怎么做，看了题解后的第一感想就是，太妙了！！！
简单说一下无定根的最小树形图的基本思路。
首先建立一个虚根 r ，让虚根连向每一个实点，权值尽量大，一般选择实边边权和+1即可，以虚根建立最小树形图。
如果得到的答案大于等于两倍的 虚根到实点距离 , 那么就是不存在。因为最多只会存在一条。具体自己yy即可。
而我们需要找出的根节点，因为存在缩点，所以直接拿 虚根指向的结点是不行的。另一条有效且方便的方法就是在 虚根连实点的时候 一般人都会按顺序连，那么只要记录边的序号，然后 序号 – 点数即可。
题意：
无定根最小树形图裸题。
思路：
见上。
AC Code
#include
昨晚多校的以为是数论的图论题，我看许学姐也是忙得不可开交肯定是没去看过的了。 看了题解发现matrix tree，以为可写，然后就跟Yasola搞这题搞了一个晚上…… 这道题用到的是求欧拉回路的 BEST THEOREM 定理，感觉国内资料相当少，不管google还是baidu都搜不到什么中文介绍，唯一搜到的是一片SGU的题目…… 这里稍微简单介绍一下…… BEST THEOREM 简介 BEST THEOREM是解决有向欧拉回路路径数量的定理，其前提条件是能构成欧拉回路，也就是每个点必须入度等于出度，(这个是要自己额外判断的……) 其表达式为 $ ec\left( G\right) = t_{w}\left( G\right) \times \prod _{v\in V}\left( \deg \left( v\right) -1\right) ! $ 其中，( t_{w}\left( G\right)…
第一道最小树形图的题，最近意外的发现，生成树的题目超级多…… 最小树形图在很早就想抽时间学一下了，因为之前看了Yasola的博客…… 昨天多校的有向图的matrix tree定理中提到了树形图，所以现在就来补一下。 这里简单介绍一下朱刘算法求解最小树形图 不错的学习资料 朱刘算法的整体思路在于在根节点确定的前提下 对于每一个点，去寻找他边权最小的入边。 在寻找结束后，有三种情况 1. 存在一个点不存在任何入边，则不存在以当前根节点的最小树形图 2. 存在若干个环，这显然不符合树形图的要求 3. 不存在任何环，满足要求且最小，得到了最小树形图。 在寻找最小入边的思路下，最大的问题就是找出结果存在若干环，朱刘算法没有避开这个问题，而是去正面解决。 解决方法是将每一个由最小入边形成的环缩为一个点，将所有指向缩点后的某一点的边权减去，缩点前环内指向该点的边权。 这个有点难描述，但看看下面的图片就很好理解了。 下面是题解。 题意： 给你几个点，几条边，问你从1结点开始的最小树形图的值。 思路： 无。模板题。 犯了一个很煞笔的错误，求得…
真是哭了，今天多校的图论题，算得上是在比赛的时候的进阶题目，A了这道就能挤开一大片那种……
没A，思路错了……
题意：
给你一棵树，要你将 { 2，3，4……n } 进行划分成 k 个集合，每个集合与{ 1 }相并后 求 最小 斯坦纳树，求和的最大值。
思路：
考虑每条边贡献值，只可能是 k 与 子树结点的最小值，将贡献值与边长相乘累加后便是答案。原因yy即可。
一边dfs得出每个结点的子树结点数，复杂度 O ( n ) 。
AC Code
#include
今天做的不太一样的状压，从去年的专题找的，看到学长并没有写是已经写过了么？ 可能是因为跟图论相关的原因吧。 题意： 给你一个简单图，让你找出简单环的数量。 附 ： 简单环就是没有重边和重点的环。 点数为 19 。 思路： 19个点，一般很容易想到状压和二维……根据数据猜算法？ 事实上我是没有想到二维的 dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ，初始对每个状态 dp [ 1<< i ][ i ] 设置为 1 对于每一个状态，固定的从最小的一位 1 作为起点，从这个起点开始扩散，如果能回到这个起点，就进行计数。 因为对于一个环，枚举起点和终点的话，会存在起点到终点，和以终点为起点的情况。 比如说 1-> 2 -> 3 ->1 和…
前几天刚写了一道状压DP入门题，结果这次就遇到了，在比赛最后一点时间一眼看破，无奈只有想法，写不来……
不过赛后尝试写的时候遇到了一个自己不会的问题，也就是说假如比赛的时候开了这道题，我也会一直卡着。
题意：
给你很多个行李的位置和起点的位置，要你把所有行李搬运到起点，一次只能搬一个或者两个，花费是距离，求最小花费。行李最多24个。
思路
状压dp，对于每一个状态，我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的，那么，我通过从小到大枚举状态，在保证我当前状态最优的前提下，由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举，找到第一个它能够搬运的行李，每次都拓展这个状态即可。
AC Code
#include
题解 2-SAT 一眼题，但是很遗憾，我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解，我个人以为，只要染色数量等于点数就是可行解。有哪里不对的么？？ 但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。 传送门 题意 有n个人手中有n张卡，每个人说两句话，有一句必定为真，有一句必定为假。说了2-sat一眼题…… 两句话分别说，我自己手上是几号卡，别人手上是几号卡，保证不存在相同的陈述。 思路： 对于每两个人 i 和 j 的陈述，进行判断，如果产生矛盾，则建边。 产生矛盾是指两个的陈述，主语或者谓语有一个不同就产生了矛盾。 eg 1 号 手中有 2 号卡 < —- > 1 号手中有 3 号卡 1 号 手中有 2 号卡 < —- > 2…
好题！！！！ 这道题我整整想了一个晚上，怎么说呢，应该还是我从一开始就没想复杂，考虑得简单了，然后后面就写的很复杂了…… 其实我在写到一半的时候就突然想到我的状态转移方程是错的，然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰…… 题意： 一个90后都玩过的空间游戏吧，记得叫 是男人就下一百层 ，题意不是很好描述，可以自己去玩玩。 思路： 先说一下我最开始的想法，不想看的直接往下翻。 这道题我一看，诶，水题！我只要每次移动都保证当前层所花时间最少，类似记忆化搜索，一步一步推过去就能保证我的答案最优…… 首先这个思路的确是对的，但却忽略了一个细节，从我以前走过的层到我当前层，有个位置上的关系。 就是说当我每次得到当前层时间最短的时候，我必须把落下的相应位置给确定下来，否则，若存在重复的最优时间，当前下落位置不同，会影响之后的时间。这是显然的。 而我要想补救我的思路，那我必须记录所有的位置，虽然这个位置数量不会超过2，但这实现起来就很烦。 正解： 其实正解是很简单的，我只要反向思考就可以了。就是记录当前层到底层的最短时间。考虑当前层到中…