最小割建图好题！！
昨天比赛的最小割，当时没看出来，实际上需要建图转化一下，这道题非常显然！！！
比赛后不想看题解，问了一下Yasola，指点了一下马上懂了！！
题意：
有n×m的地图，地图上最多有6个国家，现在K国要修长城，来防御敌对国家，6个国家中除了K国和一个敌对国家，其余国家都是友好国家，想要进供从而使得自己在长城防御范围内。建立长城的每一个花费都已经给出。
问最小花费。
思路：
将地图以外的地方视为敌对，将一个地图上的格子与其上下左右相连。
对于一个长城，实际上就是将K过与友好国家 与 敌对国家割开的最小割。
又因为点数和边数都很少，最多通过枚举 2^5 枚举将友好国家包围的情况，每次求一下最小割即可。
AC Code
#include
算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一篇博文中提到过，ACM中求强联通分量的常见算法有三种： 1. 暴力 2. Tarjan 3. Kosaraju 其中暴力和 Kosaraju 算法在求强联通分量的同时，可以直接输出可行解，而Tarjan则需要通过额外的拓扑排序来得出可行解。 简单说一下 Kosaraju 的基本思路： Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。 对于一个强联通分量，将它的所有边反向，那么它依然是一个强联通分量。 因此，我们通过两边dfs，第一遍dfs求出整张图的拓扑序，第二遍dfs按照拓扑序通过反向边进行拓展。 这个地方就非常巧妙。因为在按照拓扑序遍历的过程中，对于一个点，如果它是一个强联通分量的一个点，那么除开原先遍历标记过点，必然会存在拓扑序在该点之后但仍然指向该点的一个点。 好难表达，yy很容易 题解 题意： 有一群牛，给你很多个关系，一对关系 a -> b 表示 a 认为 b 是肥宅，问被所有牛公认为肥宅的牛有几头。…
第一次刷到HDU第一名，趁现在没人比我高，截图来一发！！！！ 对于这道题，我只想说一个字 妙！！！！ 题意： 给你四个点，(1,2),(2,3),(3,4),(4,1)之间都有一条无向路径，让你从 2 号点出发，最后回到2号点，同时使得走过的距离大于等于 k ，并且 最小。 k很大，最大达到 1e18 ，四条路的范围不大于 3e4 。 思路： 这道题真的是太妙了！！！ 说一下我比赛前后的思路，这里我称 从 起点 2 回到 2的回路为 E 回路。 先说一下我比赛的思路： 一开始我的思路是这样的，首先不考虑单纯的往返，那么E回路就有7种情况。 那么我考虑复杂度的话最多的就是4点成环且只有4条边的情况，对于这条已有的E回路，我们可以在任意一条路径走来回走，使得路径长度增大。 那么我们就可以将问题转化成为…
今天多校的第一锅…… 这套题真是神奇，明明都是Claris出的，涉及图论的居然有4道…… 而且就这道题来说，有一个卡点真的是很让人觉得奇妙。 题意： 给你一个两边点数相同的二分图，左边的点都会连接右边两个不同的点。 求 每一个完美匹配的边权积 的和。 思路： 真特么神题…… 一开始我看到这题，潜意识的想到网络流，看到点数这么多认定不可能是网络流。又通过每个左边集合的点都有两个选择，互相矛盾想到2-sat，但需要输出所有可行解又十分困难。于是我猜测，最多只有两个方案。但是被队友反驳了……最后就没出…… 其实基本思路已经对了。的确是求2-sat的所有可行解。但是会有一些优化的地方。 一开始，我们对于右侧的点，如果他的入度为 1 ，那么我们的选择是确定的。用这个方式对整张图进行拓扑排序。最后获得左右两侧都有 m 个点，并且右侧的点的入度都大于等于 2 。 因为此时左侧只有 m 个点了 ，那么左侧的出度和也就是右侧的入度和 就是 2m ，因此右侧的每个点的入度都为 2。 对于这样的图，图中的每一个强联通分量内，他的可行方案的确是两个，自行yy即可。…
今天在回寝室之前A的最后一题，是前年多校的一道最小树形图。
老实说，一开始看到这题第一想法，是将所有终点练到超级汇点，然后跑最短路。冷静了一下发现完全搭不上边……
比如说当你学到了某一个课程的level 5 ，那么该课程的level 4 ，level 3都是无消耗可达的。
是的，说到这，学过最小树形图的十有八九都会有思路，将同一课程高level指向低level，消耗为 0 。建立超级汇点连接每一个课程，再将培训班建边，跑一跑朱刘即可。
题意：
小明有n个课程，每个课程有个理想的level，他想通过补课来达到这些level。补课形式是你在a课程达到某一个level，那你补完之后就会在b课程直接达到 另一个level，花费给定。
求最小花费。
思路：
见上。
AC Code
#include
妙啊！！
无定根的最小树形图，没想出来怎么做，看了题解后的第一感想就是，太妙了！！！
简单说一下无定根的最小树形图的基本思路。
首先建立一个虚根 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结点开始的最小树形图的值。 思路： 无。模板题。 犯了一个很煞笔的错误，求得…