昨晚疯狂掉分的第四题，其实比第三题还简单……
搞不懂cf又不按套路出牌了……先是来一个巨简单的，让每个人都不得不去签到，随后是坑题，然后是压轴题，再然后才是普通题，难题……
题意：
给你一棵树，每次询问3个点，要你求出3个点两两构成的路径中选出两条，使得他们相交的长度最长。
思路：
这道题并不难，先求出LCA，再分类讨论一下即可，但是但是但是但是！！分类的情况会非常非常多，就图而言就有4种，还要考虑各自的位置。
必须得总结一下，不然跟着写会疯掉。
考虑让每个点为两条路径的相交点，分三种情况讨论。
而每种情况中，当两个路径各自的lca相同时，除了该点的所在的路径以外只要求出另外两个点的lca长度 – 三点lca 路径长度即可。
否则，就只剩下第三个点为另外两点的父亲这一情况,所以长度为 根节点到所讨论的结点距离 减去 非父亲结点的另外两个结点的 lca 的距离。
AC Code
#include
多重匹配模板题……也是从薛昊那偷来的题…… 貌似有更好的做法……看到了什么二进制压缩什么的…… 这题数据很大，时间卡的很紧，使得我对模板使用了解更深了一点。 题意： 地球上有n个人要移民，有m的星球可以提供移民，这些人都很挑剔，只去自己感兴趣的星球，问是否存在一个方案使得每个人都能去自己感兴趣的星球。 每个星球容纳人数有限。 人数1e5，星球数 10。 思路： 二分图多重匹配裸题。这里如果你对模板使用比较了解肯定是一发水过的…… 这里要对数组强调一下。 记 左元数组 l ,右元数组 r * mat[n][m] 二维可达矩阵。 * link[m][n] 二维连接矩阵，记录每个 r 元素 连接的 l 元素 * vis[m] 单次dfs的访问记录数组 * vlink[m] 记录每个 r 元素连接的 l 元素数量…
本来以为是一道好题……
没想到xjb被我水过去了……
题目看不大懂去找题解看题意，都说什么LCA，醉了……真的不喜欢数据弱的题目。
题意：
给你一棵生成树，再多给你几条边，要你只能删除一条生成树的边的同时，最少删掉多少条边才能使得整张图图不联通。
思路：
一个很显然的规律就是，找到生成树上度数为1的点，再比较其他度数和即可……
这里有个漏洞，就是可以在删掉一条生成树上的边就可以分割整张图，简单说，就是桥……
不是很懂他们LCA的思路，水过了就不想思考了。我倒是觉得，直接tarjan缩点预处理一下，再特判一下缩点后的点数即可。
AC Code
#include
这道题本来是放在二分图多重匹配的专题上的…… 但是在二分图上没怎么想出来，在网络流上一下子就有了想法…… 因为本来二分图问题就是网络流的子问题么……我如是安慰自己…… 题意： 一个刚出道的女演员有 n 部电影要拍，一部电影要拍多天，一天只能拍一部，给定每部电影安排的日期，和截止时间，问能否安排妥当。 思路： 这道题在网路流建图上一开始我是这样建的。 记录一周中每天限制周数最大的，作为电影与日期的流量，源点到电影流量为拍摄天数，日期到汇点容量为各自的限制周数。 这里有一个错误的地方，我拿个数据就很容易明白。 3 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 inf inf…
二分图多重匹配第二题，提前再说一句，二分图匹配用网络流均可解
因为受了ysk学长博客的影响，开始习惯用宏定义写代码，有点不习惯，搞得我在控制范围上浪费了一些时间。
题意：
n头牛，m个牛棚，每头牛各自有各自喜欢的牛棚，给出喜欢的牛棚顺序，每个牛棚容量，要求他们的喜欢范围最小。(就是所住牛棚的最大喜欢值 – 最小喜欢值 最小)
思路：
二分牛棚数 ，并枚举范围起点，判断可行性 这么暴力？
AC Code
#include
最近网络流有点写累了，就尝试着写了一下二分图。
这是我第一道二分图多重匹配的题目，基本上是看着模板敲的……
因为中间在main函数内外都定义了n,m ，搞得我debug了好久……
二分图多重匹配想比喻二分图单匹配来说，只是多加了几步，本质上还是一样的。基本上看代码就能看懂。
题意：
有个女神的备胎很多，每次找备胎都很麻烦，搞得她很困扰。现在女神想把他的备胎们分成m组，根据关系有的必须放在特别的组，但是女神数学不好，于是女神随手找了个备胎帮助计算，在满足条件的情况下有个组内人数max，现在要你求最小的max。
思路：
二分人数+多重匹配。
最大流也可。二分到汇点的容量即可。
这里有个小麻烦，就是有不定数量的数字。
一般人会立马想到，最麻烦的getchar() , 好一点的想到 stringstream
这里比较合适的应该是 一起输入一个数字和字符，如果字符是换行符号则退出。
AC Code
#include
两道方格取数，第一道数据较小，可用状压dp求解，但是第二道数据增大1.5倍，状压就吃力了。 其实这里可以转化成最小割求解。 题意： 给你一个矩阵，矩阵中的每个数都有一定权值，当你取出其中一个数，与他上下左右相邻的数就不能被取。问你能取出的最大权值。 思路： 首先熟悉dp的人马上会想到。这是在一维相邻元素取舍的二位拓展。dp的思路易得。 但本人并不熟悉dp，只知道可写…… 这里说的最小割解法。 先补一下所需前置知识。 * 二分图点权最大独立集：带点权二分图G中的一个子集V，其中一条边的两个端点不能同时属于V，且V中点权和最大。 * 点覆盖集：无向图G的一个点集，使得该图中所以边都至少有一个端点在该集合内。形式化的定时意思点覆盖集为V’∈V，满足对于所有的(u,v)∈E,都有u属于V’或v属于V’成立，即至少一个成立。形象的说是若干点“覆盖”住了与他们邻接的边。这些边恰好组成了原边集。 * 最小点覆盖集： 在无向图G中，点数最小的覆盖集。 * 最小点权覆盖集：在带点权无向图G中，点权之和最小的点覆盖集。 那么显然，点覆盖集的补集就是独立集，…
非常感谢这道题，准确的来说应该是这道题的数据。这道题其实是很简单的。
题意：
一堆箱子围成一个圈，每个箱子里面初始没有或有几个球。要求最后每个箱子里面最多一个球。每次转移球只能转移到相邻的箱子，转移一个球，需要花费1。问最小花费。
思路：
最暴力的思路是每个球对其他所有球都建立一条边，费用为最短距离。
但是有个显然的特点是，a -> b 与 a-> k , k-> b 的花费是相同的。所以我们只要在相邻的箱子建边即可。容量 inf ，费用为 1 。
建立源点连接有球的箱子，容量为 球 数，花费为 0 。箱子到汇点容量为 1 ，花费为 0 。
AC Code
#include