不知不觉我们相识也快两年了

非常感谢你这两年对我的陪伴与支持

也非常抱歉给你带来了一段不那么愉快的回忆

希望你能在将来的时光里找到自己的归宿，实现自己的梦想

祝你幸福

生日快乐！

无聊来UOJ转转看到自己被hack了

各种不爽，顺手改了改又A掉了

你们就当是已死选手诈尸吧

http://uoj.ac/submission/140874

upd: 1ms god!

http://uoj.ac/submission/141742

I love bx2k.

事情是这样的，在秦心学姐沉迷于高考的时候，遇到了一个数学题。

求证:$\frac{1}{2\times3}+\frac{1}{4\times5}+...+\frac{1}{2n\times(2n+1)}<\frac{1}{3}$

因为秦心学姐会泰勒展开，所以知道那个式子的极限是$1-\ln2$。

但是秦心学姐并不满足于求出这个式子，所以秦心学姐提出了一个问题：

$\sum_{i=0}^\infty\prod_{j=1}^k\frac{1}{ik+j}$的值是多少？

以下是我的推导日天过程

\begin{align*} \sum_{i=0}^\infty\prod_{j=1}^k\frac{1}{ik+j}&=\frac{1}{(k-1)!}\sum_{i=0}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=\frac{1}{(k-1)!}\sum_{i=0}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\int_0^1x^{ik+j-1}dx \\ &=\frac{1}{(k-1)!}\sum_{i=0}^\infty\sum_{j=0}^{k-1}(-1)^jC_{k-1}^j\int_0^1x^{ik+j}dx \\ &=\frac{1}{(k-1)!}\sum_{i=0}^\infty\int_0^1(1-x)^{k-1}x^{ik}dx \\ &=\frac{1}{(k-1)!}\int_0^1\sum_{i=0}^\infty x^{ik}(1-x)^{k-1}dx \\ &=\frac{1}{(k-1)!}\int_0^1\frac{(1-x)^{k-1}}{1-x^k}dx \\ &【前方高能预警】 \\ &=\frac{1}{k!}\int_0^1\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{1-\varepsilon^j x}dx &(\varepsilon=e^{\frac{2i\pi}{k}}) \\ &=-\frac{1}{k!}\sum_{j=1}^{k-1}\frac{(1-\varepsilon^{-j})^{k-1}}{\varepsilon^j}\ln(1-\varepsilon^j) \\ &=-\frac{1}{k!}\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\ln(1-\varepsilon^j) \\ &【什么？你以为这就完了？图森破】 \\ &=\frac{1}{k!}\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\sum_{i=1}^\infty\frac{\varepsilon^{ij}}{i} \\ &=\frac{1}{k!}\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}(\varepsilon^j-1)^{k-1}\varepsilon^{ij} \\ &=\frac{1}{k!}\sum_{i=1}^\infty\frac{1}{i}\sum_{j=1}^{k-1}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\varepsilon^{jl+ij} \\ &=\frac{1}{k!}\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l\sum_{j=1}^{k-1}\varepsilon^{j(i+l)} \\ &=\frac{1}{k!}\sum_{i=1}^\infty\frac{1}{i}\sum_{l=0}^{k-1}(-1)^{k-1-l}C_{k-1}^l(-1+[(i+l)\bmod{k}=0]k) \\ &=\frac{1}{k!}\sum_{i=1}^\infty\frac{1}{i}(\sum_{l=0}^{k-1}(-1)^{k-l}C_{k-1}^l+k(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}) \\ &=\frac{1}{(k-1)!}\sum_{i=1}^\infty\frac{(-1)^{(i-1)\bmod{k}}C_{k-1}^{(i-1)\bmod{k}}}{i} \\ &=\frac{1}{(k-1)!}\sum_{i=0}^\infty\sum_{j=1}^k(-1)^{j-1}C_{k-1}^{j-1}\frac{1}{ik+j} \\ &=\sum_{i=0}^\infty\prod_{j=1}^k\frac{1}{ik+j} \\ &【登登登！成功推回来啦！】 \end{align*} 所以问题来了，这个式子还有更简洁的结果嘛？

快到NOI了老年选手要开始复习了

阅读更多……

http://uoj.ac/hack/1940

阅读更多……

貌似成为了卡评测姬的罪人

阅读更多……

http://uoj.ac/submission/59143

留坑待填 :3

阅读更多……

讲完最大匹配开始讲最大权匹配了。

首先对于所有最大权匹配，可以通过加边加点的方法把问题转化为最大权完备匹配，所以我接下来讲的都是最大权完备匹配而不是最大权匹配。

现在设左边右边都有$n$个点，左边第$i$个点和右边第$j$个点之间边的权值是$w(i,j)$。

先来介绍顶标的概念，顶标就是把整个二分图的每一个点上标一个值，用$labL_i$表示左边第$i$个点的顶标，$labR_j$表示右边第$j$个点的顶标。

那么一组合法的顶标需要满足对于任意一组$(i,j)$有$labL_i+labR_j>=w(i,j)$。也就是说$\sum labL_i+\sum labR_j>=\sum w(i,j)$，于是我们就可以不断调整顶标，使得顶标的和达到最小值，此时$\sum labL_i+\sum labR_j==\sum w(i,j)$，也就是说我们找到了边权和最大的完备匹配。

引用一段话：

設定上限，然後不斷降低上限，降低到極限就碰到最大值了。原本一個求最大值的問題，變成了一個求最小值的問題。這是很實用的數學轉換。

【註：以 Linear Programming 的觀點來看，這個轉換正是 primal problem 與 dual problem 之間的轉換。】

這個轉換有個重要目的：操作 vertex labeling 而不操作 edge labeling ，藉此減少調整權重的時間。

現在只要求出一組總和最小的 vertex labeling ，就得到最大權完美二分匹配。

于是接下来就要求出一组总和最小的顶标。

接下来给出等边的定义，等边就是一组$(i,j)$满足$labL_i+labR_j==w(i,j)$的边。

由于二分图最大权完备匹配的最终结果中的匹配边肯定都是等边，那么我们要找的增广路就变成了由等边构成的增广路。

但是如果在当前图中找不到由等边构成的增广路而匹配数没有到$n$时怎么办呢？那就只能通过调整顶标来让图中的等边变多从而找到新的增广路。

那么设$v=min(labL_i+labR_j-w(i,j))$其中$i$是交错路径树中的左边点，$j$是非交错路径树中的右边点。我们让所有交错路径树上的左边点$i$的$labL_i-=v$让所有交错路径树上的右边点$j$的$labR_j+=v$，就可以在保证顶标合法的前提下增加至少一条等边。

如果这个$v$更大的话，顶标就会不合法，如果这个$v$更小的话，就不会增加新的等边，因此每次顶标改变的值都是固定的。

那么接下来简要说一下算法流程(注意我会把$slack$的优化一起说，也就是说我说的是$O(n^3)$的做法)

首先初始化一组合法的顶标，一般是$labL_i=max(w(i,j))$，$labR_j=0$。

然后对于每个左边的点，把他当成起点BFS找增广路。

执行以下步骤直到找到增广路。

while(true){

那么对于每次队列中队首的左边点$u$，首先让它出队。

然后对于不在交错路径树中的右边点$v$，如果$labL_u+labR_v==w(u,v)$，那么我们找到了一条新的等边。

如果$v$没有匹配点，我们就找到了一条增广路，那么进行增广并结束本次增广路的查找。break;

如果$v$有匹配点，就把$v$的匹配点加入队尾继续寻找增广路。

如果$labL_u+labR_v>=w(u,v)$即$(u,v)$不是等边，就用$labL_u+labR_v-w(u,v)$更新$slack_v$

如果在上述过程中没有找到增广路，那么对于所有不在交错路径树中的$v$，找到$slack_{min}=min(slack_v)$

对于所有在交错路径树中的$u$，$labL_u-=slack_{min}$，对于所有在交错路径树中的$v$，$labR_v+=slack_{min}$

因为$labL$改变了，所以$slack$也会改变，因此对于所有不在交错路径树上的$v$，$slack_v-=slack_{min}$

然后对于所有右边的不在增广路径树中的点$v$，如果$slack_v==0$，那么说明找到了新的等边。

于是设$u$为使$slack_v==0$的左边点，像之前找交错路径树一样讨论：

如果$v$没有匹配点，我们就找到了一条增广路，那么进行增广并结束本次增广路的查找。break;

如果$v$有匹配点，就把$v$的匹配点加入队尾继续寻找增广路。

如果在上述过程中仍没有找到增广路，那么就把现在仍在队列里的点当成起点继续找增广路继续调整顶标。

}

最后把所有顶标累加就是最大权完备匹配的结果啦~

那么二分图最大权完备匹配就讲完咯

thx bx2k.

另外欢迎大家来问我和二分图最大权匹配有关的问题

My Chinese Sucks.;w;

谢谢大家！

继续开坑~btw,I love bx2k.

这次来讲HK算法。我二分图最大匹配只会HK是不是药丸QwQ

和所有匹配算法一样，中心思想还是找增广路。但是找增广路之前，我们要把整个图分层。

说到分层，Dinic选手是不是想到了些什么我是isap选手，是的，就是按Dinic的方法分层。

首先把左边所有没有匹配的点全部加入队列，层数为0，再把这些点通过非匹配边连向的右边的点的层数标为1，但是不加入队列，而是对于右边这些层数为1的点，如果它们有匹配点，就把匹配点再加入队列，层数标为2，后面的以此类推。

看到这里是不是觉得和一般图最大匹配有点类似呢，‘只用把一类点加入队列’，这样做才能体现出‘走一条非匹配边走一条匹配边’的增广路。

于是和Dinic一样，分层结束之后就可以找到每个点出发的最短的增广路，这也就是分层的意义。

接下来分类讨论，如果所有能搜到的右边点都有匹配点，那么不能再找到增广路了，算法结束。

否则，对于每个层数为0的左边点，找到他们连出去的最短的增广路，也就是每次走让层数加一的边的增广路。

可证明，一共只会执行O(sqrt(n))次上面的操作，于是总复杂度就是O(sqrt(n)$\times$(n+m))的。

然而用Dinic做也是这个复杂度，其实这个算法就是Dinic的二分图简化版？

这就是HK算法咯，是不是一个又好打又快的算法丫~还在犹豫什么，快去学吧！

其实具体细节和技巧依旧很复杂的大家就去看代码吧

另外欢迎大家来问我和二分/一般图最大匹配有关的问题

感觉语文好差啊，写的文章好烂啊，肯定又要被D了QwQ

顺便说一句，我写的所有文章按Ctrl+A全选之后都会看到彩蛋

=w= 看到这句话的都是呆呆哒的神犇！ hhh

代码合集：http://uoj.ac/submission/52814

二分图最大匹配：已完成 讲解：http://qwx.blog.uoj.ac/blog/1384

一般图最大匹配：已完成 讲解：http://qwx.blog.uoj.ac/blog/1227

二分图最大权匹配：已完成 讲解：http://qwx.blog.uoj.ac/blog/1385

一般图最大权匹配：已完成

↑有时间再补吧