早上起来心情很好。【悲剧的前奏。。。

--------------------------------------------------------------------

考试的时候只写了第二第三题，第二题写了个满分算法，第三题写了一个随机化算法。结果第二题的BFS写跪了。然后就跪了。然后运气不佳随机一分都没有。然后就没有然后了。

----------------------------------------------------------------------

第一题：

给出一个无根树。树有N个点，边有权值。每个点都有颜色，是黑色、白色、
灰色这三种颜色之一，称为一棵三色树。
可爱的Alice觉得，一个三色树为均衡的，当且仅当，树中不含有黑色结点
或者含有至多一个白色节点。然而，给出的三色树可能并不满足这个性质。
所以，Alice打算删去若干条边使得形成的森林中每棵树都是均衡的，花费
的代价等于删去的边的权值之和。请你计算需要花费的代价最小是多少。

(n<=300000，5组数据以内，时限2s)

【树形动归。状态还要加上子树中白色与黑色节点的颜色。 考试的时候怎么没想到呢- -

第二题：

给出一张无向图，每条边连接两个不同的点，且长度是已知的。而逃犯Frank选择了一条
从城市1到城市N的最短路径作为他的逃跑路线。
为了阻止Frank，共和国总统决定在某些点的边的出入口设立检查
点，在Frank经过检查点时将他逮捕。
举例来说，如果有一条边连接点u和点v，在这条公路的城市u
或城市v的出入口设立检查点，那么Frank经过此边时就会被发现。
特别的是，由于点N实际上处在反对派的控制下，所以不能在点N设立
检查点。

然而在任何城市设立检查点都需要一定的费用。更具体的，若在城市u设立
k个检查点，就要花费Au乘以k的代价，其中Au是城市u的相关参数。值得注意
的是，这个代价与这k个检查点具体设在哪些公路的出入口无关。于是，总统责令情报局拟定一个方案，花费最小的代价使得无论Frank选择
哪条最短路线，都会在（除城市N以外）某个城市的高速公路出入口被发现。

注意，我们称两个方案不同当且仅当存在某城市k，两种方案中在城市k的
检查点的设置（而不仅是数目）是不同的。

求解两个问题：一、最小花费。二、最优方案是否唯一。(V<=400,E<=4000)

【网络流。第一问和最小割模型很像，但是不完全相同。对图跑一次spfa，求出每个点到1的最短路径，只保留那些du+c(u,v)=dv的边，然后将其流量定为min(Au,Av)，且An=INF，那么此网络的最小割即最大流即为最小花费。可惜只做第一问一分都没有。第二问事实上是在问此网络的最小割方案是否唯一。有好多种方法可以做这件事。

{I、枚举每一条在当前最小割内的边，将其容量+1，广搜一次看看有没有增广路。如果存在增广路那么说明原边一定在此图的任意一个最小割方案里。原因如下，这条边的容量改变对那些不包含这条边的最小割方案没有影响，也即原图的最小割在容量改变前后不变。如果存在这种方案，那么一定找不到增广路。因为最小割=最大流。所以只要当前最小割里的每一条边都在任意最小割里，最小割就是唯一的。效率O(E^2)。}

{II、以下操作均作用于求了最大流之后的残量网络。从源点BFS标记每一个到达的点。从汇点逆向BFS标记每一个到达的点。如果存在既在当前最大流上，又没有被标记到的点，那么此网络的最小割是不唯一的。充分性和必要性都证明一次即可。注意最小割的方案一定是（最大流中满载的边）的一个子集。效率O(E)}】

第三题：

Alice是个很有魅力的人，她一共有N个好朋友。而她的这些好朋友互相之
间可能认识，也可能不认识，还可能有矛盾。
这N个人之间是否认识是无所谓的，但是如果两个人之间存在矛盾就会产生
一些问题。这里，矛盾关系是双向的。
Alice知道，如果她邀请的任意一个好朋友小X在宴会上仅看到一个与小X
有矛盾的人小Y，就会不太高兴，不过可以假装没看见。但是，如果小X再次
看到另一个与小X有矛盾的人小Z，小X就会很生气并离开宴会。
为了防止这样的情形出现，Alice决定只邀请她的一部分好朋友参加宴会，
使得对于这些人中的任意一个人，至多有一个与他（或她）有矛盾的人同时受到
邀请。这样，就不会有人中途离开宴会了。问最多可以同时邀请几个人。(n<=40,50组数据以内)

【先证它是NP问题，即它的一个解可以在多项式时间内判断其是否合法。这是显然的。然后再证它可以规约到一个NPC问题即任意图的最大独立集。所以这是一个NPC问题。标程搜索。然后又证明了存在一个最优方案使得所有（只与一个人有矛盾的人）都被邀请。在此结论的基础上剪枝搜索。然后昨天随机AC第三题的随机帝今天又AC了此题。用的还是随机。神一样的男人。】

----------------------------------------------------------------------------

悲惨下场。