若水而净万物

题目一：道路重建(USACO_2002_Feb02 Rebuilding Roads)（PKU1947）(程序附后)
题目大意是给一棵树，要去掉最少的边，使一棵子树从中分离出来，且这棵子树要恰有B个节点。

很容易想到此题为树型Dp,用状态[i,j]来表示以节点i为根，得到一棵j个节点的子树至少要去多少条边（请注
意，这里定义的节点i是这棵子树的根,所以一定包含这棵去掉一些边后所得到的j个节点的子树里面）。怎么
转移呢？如果穷举i的子节点保留还是不保留，如果保留，保留多少个。那么这道题目又退化成完全的搜索了。。不难想到,因为节点i的所有子节点是一个线性结构,我们可以双重Dp!!

下面讲一下第二重的Dp:
对于一个节点i,
设它的儿子依次为1,2,....,x.再设一个状态(k,m)表示到节点i的第k个儿子,要保留m个节点,至少要去掉多少条边.这样,对于这个节点i,我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是选这个k,二是不选这个k,
1.如果不选k,那么(k-1,m)+1--->(k,m)(加1是因为不选这个儿子k,所以k和i所连的边应该断开,那么花费就要加1).
2.如果选nk,那么(k-1,j)+[k,m-j]--->(k,m)(注意,中括号所表示的状态时第一重动规所得到的状态,在这里[k,m-j]的意思就是节点k为根，得到一棵(m-j)个节点的子树至少要去多少条边)

那么就很容易转移了:(k,m)=min{(k-1,j)+[k,m-j]{0<=j<=m},(k-1,m)+1},边界自己想吧。。。。。对于这个节点i,算完所有的(1,m),(2,m),...,(x,m)后,[i,m+1]就等于(x,m)(这里+1是因为i这个节点要保留),每次算出(i,B)后,动态更新下ans就行了...Dp时候的顺序可以记忆化搜索,也可以按后序遍历的顺序进行Dp...

尽管讲了这么多,感觉还是有很多细节问题没有讲清楚,这还是要自己思考一下的,这里只是提供了一个大致的
思路而已...(更多时候，这个思路可能只有作者本人才能看懂的--!)。如果谁有更好的方法,欢迎留言:)

题目二： 贪吃的九头龙（NOI2002_DAY1）
题目大意是给一棵树，再给m种点，这些点要覆盖这棵树的所有节点，且每种种类的点至少要用一次，还规定第一种点必须恰好用K次。这棵树的每一条边都有一个权值（每条边的权值可能不同）。对于某条边，若这条边的两个顶点种类相同，则总权值需要加上这条边的权值。问总权值最少是多少。（可能描述的有些模糊，不懂的看一下原题吧。。。）

首先，要明确一点，就是除了m=2的情况外，如果有的边的两个顶点种类相同，那么这种种类一定是第一种！这能保证解是最优的！发现了这个，就意味着问题解决了一半了。接下来就是状态表示了。。
不难想到用[i,j]表示节点i，恰有j个节点被第一种类的点覆盖，总权值最小是多少。不！这还不够！我们必
须增加一维！这一维不是0就是1，0表示节点i被第一种类的点覆盖，1表示节点i被非第一种类的点覆盖（就是被第二或第三...或第m种类的点覆盖啦--！）。即状态是[i，j，0/1]怎么转移？这不禁联想到上面的第一题，如果还是这样进行一重Dp,那也就是退化成单纯的搜索了。。我们必须进行双重Dp!!

下面还是讲一下第二重的Dp:
还是和上题一样，对于一个节点i，它是0或1类型的。这里只举0类型的例子（即不妨假设节点i被第一种类的点覆盖）。我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是这个儿子类型是0,二是这个儿子的类型是1。
转移就不细讲了。因为涉及到很多很多的细节问题，并且不把这些细节问题讲清楚的话，转移就讲不清楚。而讲清楚这些细节问题至少需要1000+个字。所以就不详细展开讲了。。。。-_-！-_-！-_-!。。。。

总结一下。这两道题都是TreeDp,都是需要双重Dp.可以说,它们两的本质是相同的.可是,不同在哪呢?为什么第二题《贪吃的九头龙》要再加一维呢?深入思考,可以看出它们两的转移方式不同,即option不同.对于第一题,转移的时候是对边而言选还是不选的.对于第二题,转移的时候是对点而言选0类型还是选1类型.而状态是记录在点上,而不是记录在边上.所以第一题只要二维而第二题要三维.换句话说,如果我们表示状态的时候把状态记录在边上,那么第二题只要二维而第一题要三维了。上述的一段话正是本文想要说明的关键部分，有些问题虽然形式不同，但本质相同，所以只有把握本质，深入思考，才能豁然开朗。。。。。

刚搞到一个code_to_html的软件Highlight Code Converter，效果感觉不错：）。故把上述第一题的代码附上。

P.S.第二题我写了7KB,很烂,所以不发上来了.

CODE:                                                 

..........

 

我觉得写的东西不应该是单纯的解题报告，而是应该把自己的思想和思维过程表达出来，流露出来给自己看，给自己不断思考，以此来理清思路，总结经验，不断提升。

这道题最先的想法是搜索，由于每个节点有A或B两种状态，那么总共有2^（2^n）种状态，用这种方法在不及多想的情况下可以过4个点。遇上有关树的题目，首先想到的是树型DP,但是这道题并没有很清晰的表明父节点与子节点的关系，而是告诉了每一对叶子节点的关系。能不能有所转化呢？分析题目中给出的那张表可以很容易的发现每一个叶子节点与其祖先节点的关系，从而把计算每对叶子节点的费用转化成计算各个独立的叶子节点的费用。这个很显而易见的关系是，对于一个非叶子节点i，
<1>若它所管辖的叶子节点中A比B多 或者 它所管辖的叶子节点中A和B一样多，那么对于它所管辖的每一个叶子节点k来说，若这个叶子节点k是A类型的，那么这个叶子节点在这个i节点上所要的费用就是0，若这个叶子节点是B类型的，那么这个叶子节点在这个i节点上所要的费用就是sigma(f[k,j]),其中j节点满足j是叶子节点 并且 j和k的最近公共祖先是i.
<2>若它所管辖的叶子节点中B比A多，那么对于它所管辖的每一个叶子节点k来说，若这个叶子节点k是B类型的，那么这个叶子节点在这个i节点上所要的费用就是0，若这个叶子节点是B类型的，那么这个叶子节点在这个i节点上所要的费用就是sigma(f[k,j]),其中j节点满足j是叶子节点 并且 j和k的最近公共祖先是i.

至此，已将每对叶子节点的费用转化成计算各个独立的叶子节点的费用了^^.
接下来就是想DP的状态表示了。首先肯定有的一维是当前的节点i。但为了从i的左儿子的状态和i的右儿子的状态转移至i的状态，一维显然不行，必须增加维数。可是，还有的维是什么呢？显然有的一维是当前的节点i所管辖的叶子节点中A类型有多少个（既然A类型有多少个知道了，很容易知道B类型有多少个。），难道说这样两维就可以推了吗？试试看，用opt[i,cura]表示以节点i为根的子树，节点i所管辖的叶子节点中A类型有cura个的最小费用。。不对！这不满足最优子结构！（即i的左儿子的状态和i的右儿子的状态不能转移至i的状态！！（可以尝试转移，发现不行）），必须再加一维！这维是什么呢？———用数学归纳法可以很快推出此维即i的祖先中A多还是B多（比如i是第五层，那么i有4个祖先，用"0"来表示A多，用"1"来表示B多,那么这一维状态有0000，0001，0010，……共2^4种），至此，状态表示大功告成，状态转移也就迎刃而解了：
用(i,cura,fathers)表示以节点i为根的子树，节点i所管辖的叶子节点中A类型有cura个，他的祖先的状态为fathers(这个fathers其实是一个01串，可以把它转成十进制数，这样方便。)，叶节点所需要的最小费用。。转移方程就不写了。 还有一点要注意的是实现的时候要用滚动数组，否则也只能对4个点。。。。
给我的两点启示是<1>Dp时不能转移可以考虑增加维数〈2〉Dp时状态表示通常是在当前状态时的最优解，而这个在当前状态时的最优解有两种，一种是推导至当前状态时的最优解，另一种是推导至当前状态时全局的最优解。本题恰恰选择了后者，这一点很值得留心注意。 
 
程序写完。。又长又恶心。。还只能拿80分，FT。

MINCUT—MAXFLOW
建模还是感觉有些困难。一开始以为是最小费用最大流，由于要获益最大，可以把费用全部改成负号，然后就不知道怎么做了。还是看了解题报告，才有所领悟。
个人觉得看到网络流的题目，建模时要往这几个方面思考：
1。点的个数要尽可能少 2。最大流 3。最小割 4。最小费用最大流 5。最小覆盖 6。最大匹配 7。最优匹配
一切包含于简单之中，建模时要尽量往简单的方面去思考，不能太complicated。。
 
编完之后只能对8个点。。。关键还是图存不下。。应该使用前向星的。。