HDU 6073 Matching In Multiplication

By NodeKey in ACM on

今天多校的第一锅…… 这套题真是神奇，明明都是Claris出的，涉及图论的居然有4道…… 而且就这道题来说，有一个卡点真的是很让人觉得奇妙。 题意： 给你一个两边点数相同的二分图，左边的点都会连接右边两个不同的点。 求 每一个完美匹配的边权积 的和。 思路： 真特么神题…… 一开始我看到这题，潜意识的想到网络流，看到点数这么多认定不可能是网络流。又通过每个左边集合的点都有两个选择，互相矛盾想到2-sat，但需要输出所有可行解又十分困难。于是我猜测，最多只有两个方案。但是被队友反驳了……最后就没出…… 其实基本思路已经对了。的确是求2-sat的所有可行解。但是会有一些优化的地方。 一开始，我们对于右侧的点，如果他的入度为 1 ，那么我们的选择是确定的。用这个方式对整张图进行拓扑排序。最后获得左右两侧都有 m 个点，并且右侧的点的入度都大于等于 2 。 因为此时左侧只有 m 个点了 ，那么左侧的出度和也就是右侧的入度和 就是 2m ，因此右侧的每个点的入度都为 2。 对于这样的图，图中的每一个强联通分量内，他的可行方案的确是两个，自行yy即可。…

HDU 4966 GGS-DDU

By NodeKey in ACM on

今天在回寝室之前A的最后一题，是前年多校的一道最小树形图。 老实说，一开始看到这题第一想法，是将所有终点练到超级汇点，然后跑最短路。冷静了一下发现完全搭不上边…… 比如说当你学到了某一个课程的level 5 ，那么该课程的level 4 ，level 3都是无消耗可达的。 是的，说到这，学过最小树形图的十有八九都会有思路，将同一课程高level指向低level，消耗为 0 。建立超级汇点连接每一个课程，再将培训班建边，跑一跑朱刘即可。 题意： 小明有n个课程，每个课程有个理想的level，他想通过补课来达到这些level。补课形式是你在a课程达到某一个level，那你补完之后就会在b课程直接达到 另一个level，花费给定。 求最小花费。 思路： 见上。 AC Code #include #include #include #include #include #include #include #include…

HDU 2121 Ice_cream’s world II

By NodeKey in ACM on

妙啊！！ 无定根的最小树形图，没想出来怎么做，看了题解后的第一感想就是，太妙了！！！ 简单说一下无定根的最小树形图的基本思路。 首先建立一个虚根 r ，让虚根连向每一个实点，权值尽量大，一般选择实边边权和+1即可，以虚根建立最小树形图。 如果得到的答案大于等于两倍的 虚根到实点距离 , 那么就是不存在。因为最多只会存在一条。具体自己yy即可。 而我们需要找出的根节点，因为存在缩点，所以直接拿 虚根指向的结点是不行的。另一条有效且方便的方法就是在 虚根连实点的时候 一般人都会按顺序连，那么只要记录边的序号，然后 序号 – 点数即可。 题意： 无定根最小树形图裸题。 思路： 见上。 AC Code #include #include #include #include #include #include #include #include #include #include #inc…

BEST THEOREM ( 附 HDU 6064

By NodeKey in ACM on

昨晚多校的以为是数论的图论题，我看许学姐也是忙得不可开交肯定是没去看过的了。 看了题解发现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)…

朱刘算法入门 ( 附 POJ 3164 Command Network

By NodeKey in ACM on

第一道最小树形图的题，最近意外的发现，生成树的题目超级多…… 最小树形图在很早就想抽时间学一下了，因为之前看了Yasola的博客…… 昨天多校的有向图的matrix tree定理中提到了树形图，所以现在就来补一下。 这里简单介绍一下朱刘算法求解最小树形图 不错的学习资料 朱刘算法的整体思路在于在根节点确定的前提下 对于每一个点，去寻找他边权最小的入边。 在寻找结束后，有三种情况 1. 存在一个点不存在任何入边，则不存在以当前根节点的最小树形图 2. 存在若干个环，这显然不符合树形图的要求 3. 不存在任何环，满足要求且最小，得到了最小树形图。 在寻找最小入边的思路下，最大的问题就是找出结果存在若干环，朱刘算法没有避开这个问题，而是去正面解决。 解决方法是将每一个由最小入边形成的环缩为一个点，将所有指向缩点后的某一点的边权减去，缩点前环内指向该点的边权。 这个有点难描述，但看看下面的图片就很好理解了。 下面是题解。 题意： 给你几个点，几条边，问你从1结点开始的最小树形图的值。 思路： 无。模板题。 犯了一个很煞笔的错误，求得…

HDU 6060 RXD and dividing

By NodeKey in ACM on

真是哭了，今天多校的图论题，算得上是在比赛的时候的进阶题目，A了这道就能挤开一大片那种…… 没A，思路错了…… 题意： 给你一棵树，要你将 { 2，3，4……n } 进行划分成 k 个集合，每个集合与{ 1 }相并后 求 最小 斯坦纳树，求和的最大值。 思路： 考虑每条边贡献值，只可能是 k 与 子树结点的最小值，将贡献值与边长相乘累加后便是答案。原因yy即可。 一边dfs得出每个结点的子树结点数，复杂度 O ( n ) 。 AC Code #include #include #include #include #include #include #include #include #include #include #include using namespace…

URAL 1382 Game with Cards

By NodeKey in 2-SAT on

题解 2-SAT 一眼题，但是很遗憾，我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解，我个人以为，只要染色数量等于点数就是可行解。有哪里不对的么？？ 但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。 传送门 题意 有n个人手中有n张卡，每个人说两句话，有一句必定为真，有一句必定为假。说了2-sat一眼题…… 两句话分别说，我自己手上是几号卡，别人手上是几号卡，保证不存在相同的陈述。 思路： 对于每两个人 i 和 j 的陈述，进行判断，如果产生矛盾，则建边。 产生矛盾是指两个的陈述，主语或者谓语有一个不同就产生了矛盾。 eg 1 号 手中有 2 号卡 < —- > 1 号手中有 3 号卡 1 号 手中有 2 号卡 < —- > 2…

HDU 6041 I Curse Myself

By NodeKey in ACM on

多校第一场的小锅，因为就算给我时间我也写不出来的题……算是小锅吧，还有三个大锅在背上。 开头先说一声，薛昊这个坑比，woc，跟我说这里的k小生成树是就是先取一个最小的，连上每一条边…… 然后我在用优先队列的时候我就真的先推小的…… md debug好久才发现……醉了。 题意： 给你一个仙人掌图，要你求出前k小的生成树。将之与k相乘求和 mod 2 ^ 32 思路： 如果是一个一般图，那问题将非常困难，但他是一个仙人掌图，对于一个生成树来说，整张图的桥必定不能删掉，所以必须从每一个环中删掉一条边，而我们删掉的边要求前k大。 将每一个环的边作为集合，多个集合合并，求出前k大，这是一个经典问题。 方法是对每两个集合两两合并，将两个集合的边各自相连，用优先队列推出前k大，但这样时间和空间复杂度都很高。 一个与优先队列思想相似并且简单的方法就是，我们将旧集合维护有序，在这里为降序，并用一个优先队列存储两集合权值和。 首先将新集合的每个元素与旧集合最大元素(就是首位置)相加并加入队列。每次推出一个最大元素的时候，都将这个最大元素在新集合的原元素与旧集合相应元素的…