市赛

可能我们这边比较怪吧，联赛之后还需要搞个市赛选出市队

昨天就在现在这个机房比完了，题目很水，没有原创题，打字也浪费时间，就不贴了。本来感觉不是很理想，有一道很简单的 dp 题没想出来，只交了个贪心。
但是现在出来的是我是满分，于是乎我便不再担心自己

但是很多同学的命途多舛啊

squll，本来说是 310 的，还是很有希望，今天再对了下是 240，唉。。。其实他靠这样差，我也有点过失，考试前我还让他看看 hlpp，但最大流这种东西市赛是根本不可能涉及的。然后考试的时候忘记提醒他细心了，结果第三题他少考虑了一些情况，于是就悲剧了。

作为学长的确考试之前我应该提醒高一同学仔细读题的，结果我却没有做到这样的责任。今天各人看了下程序，有两个人高精度写错，一个人犯把 i 打成 j 的低级错误，一个人没有按照要求少输出了解数……

无语

离开这个自己喜欢的“事业”，是很难受的一件事吧？

既然如此，还是努力奋斗吧

真的希望所有人都能早点将大学定掉，学得轻松点，玩得开心点

但是，唉。。。

也许高二之后就我跟小岛两个人了吧。。。。。。。

Bless everyone

段考挂蛋

目前出来一门,数学65,刚刚过了64.8的平均分....
语文还好那个传说中作文8分的人不是我....
生物对了下选择题+第一个大题大概-15......

悲壮啊



还好rqnoj现在第二了
刷到第一之后把所有算法复习一遍...

又上rq，发了篇题解

无聊中看到某人的恐怖分子的题解
居然是硬枚举 s、t，o(N^5) 啊。。。。。。
于是就又写个了 Stoer-Wagner 算法介绍。。。。。。
这里原文照抄下吧。。。

其实话说我一开始也是最大流做滴。。。最大流即使是用hlpp也要 o(n^4) 的复杂度，要像某个题解说的枚举 s、t 就到 o(n^5) 了。。而且hlpp也不是随随便便就能写出来滴。。。

不过看清本质之后，这一题本质就是求无向图的全局最小割，这其实是有专门算法的，叫 Stoer-Wagner 算法，复杂度不超过 o(N^3)，而且代码行数很短。。真的很短

下面概略说明下算法，正确性证明略去：

首先我们定义对于不存在的边 (u,v)，w[u, v] = 0。
之后介绍经典的 Contract(a, b) 操作：
加入新点 u，对于 a、b 之外的每个点 v，加入无向边 (u, v) 并令 w[u, v] = w[a, v] + w[b, v]
完成之后删除 a、b 两点及相关联的所有边
不难看出，每做一次 Contract 操作，图的节点数减少1

Stoer-Wagner 算法的正确性基于如下定理：
一个无向图的全局最小割，等于这个图的 s-t 最小割，或对这个图进行 Contract(s, t) 得到的图的全局最小割。

定理是显然的，下面我们说明如何求无向图的 s-t 最小割：

首先定义对于点集 A 和点 u，w[A, u] 表示 A 中所有点与 u 连边的权值之和。再次说明，不存在的边视为0处理。
1. 初始化点集 A={}
2. 任意取一点 a 加入 A 中
3. 每次取 w[A, u] 最大的点 u，将其加入 A，直到 A=V
4. 可取3中倒数第二次加入的点为 s，倒数第一次加入的点为 t（无向图顺序无关紧要），则对应的 s-t 最小割为 w[U-{t}, t]

证明可以用数学归纳法，大家自己试试吧^_^

不难看出，上述 s-t 最小割算法的朴素实现是 O(N^2) 的（第三步显然还可以用最大堆优化，达到更好的时间界），而对于一个图，Contract 操作最多进行 n-1 次（此时图中只剩1个点了）。所以算法的复杂度不超过 O(N^3)

而代码行数，可想而知有多短了。。。

而且即使写错了什么，调试起来也比调试hlpp轻松多了

题目：

一个国家由n个城市组成，任意两个城市间都有一条双向的道路。如今，恐怖分子想要炸掉其中的一些道路，使得这n个城市变得不再连通，也就是说，存在至少两个城市，它们之间不可通过道路互相到达。要炸毁一条道路需要一定的代价。请你计算一下要使恐怖分子达到它们的目的，所需要的最小总代价是多少。

段氏恒等式照片一张

废话不多说，先上照片，早上亲照：


（这一次照片质量出奇的好，可能是班级光线充足的缘故）
前两次都没机会照下来，很遗憾，不过这次终于抓住机会拍了下来 ^_^ 谨留作纪念

还是写写东西吧...

发觉这个blog有很长时间没有写过东西了，现在决定还是好好利用起来吧
blog不必要像所谓空间那样，弄得花里胡哨，简洁就好
下周1、2段一，基本可以确定要挂蛋
下周日在本校市赛，估计问题不会很大。这两天打算不钻难题了，去vijos做点水题找找自信，同时晚上睡早些，补补最近一直不怎么样的精神状态。
准备今天晚上做个图论的小总结，把我了解的一些图论结构及算法都总结一下，尽量总结全一些，临考复习也方便些。
大概就这样吧。。。。这里还是真的要利用起来，不能浪费了 google 的服务啊……