题目传送门 # 题意分析： 看到这个题面，很容易想到是求二分图最大权完美匹配。 建图的话用邻接矩阵或者链式前向星都很容易，以及求最大权也很简单。 但难就难在第二个操作。 第二个操作的内容： 经典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算对于所有的完美匹配，其交集是什么。 运用 KM 或者 Dinic 都很容易求得完美匹配的幸福数，但是题目中可能出现多种完美匹配，用题目中的样例来举例。 3 1 1 1 2 1 1 1 1 1 1→22→13→11 \rightarrow 2 \quad 2 \rightarrow 1...

# P1559 运动员最佳匹配问题 # 解法 通过读到 计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大 这么一句话，你应该很快就能想到这是有关于二分图最大权完美匹配的问题。 那么二分图最大权完美匹配相较于二分图完美匹配来说，是边权有了权值，不是单纯的为了让配对数更多（或者是搜索出配对数最多的配对方法等）。 其他题解对于 KM 算法已经讲解的非常透彻了，我这里就稍微说说连边。 看到这个题目，你会发现两个人之间都有关系，即 A 对 B 有一个值， B 对 A 也有一个值，而在以往做的时候可能只会出现 A 对 B 有一个值，因为 A 对 B 与 B 对 A 的值都是给定的，那么我们...

前置知识 1 前置知识 2 （一些促进理解图可以看一下别人的） # 树剖： 前置基础：DFS 序， 树形 DP，线段树，链式前向星…… 树链剖分 就是对一棵树分成几条链，把树形变为线性，减少处理难度 需要处理的问题： 将树从 x 到 y 结点最短路径上所有节点的值都加上 z 求树从 x 到 y 结点最短路径上所有节点的值之和 将以 x 为根节点的子树内所有节点值都加上 z 求以 x 为根节点的子树内所有节点值之和 # 概念： 重儿子：对于每一个非叶子节点 (x)，在它的儿子 (y,z……) 中 以儿子 (y，z……) 为根的子树大小最大的节点 (y,z…… 中的一个) 为该节点的重儿子...

# 树形问题 为什么出这么一个博文呢：我今天听课以及题解看的不是很懂，sososo 我想写个（现在还在上课但我没读题，下课补吧……）。 P2016 战略游戏 一道简简单单的树上 DP 不想点链接那么就看这里： 题意：他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。 注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。 请你编一程序，给定一树，帮 BobBobBob 计算出他需要放置最少的士兵。 输入：第一行一个整数 nnn，表示树中结点的数目。 第二行至第n+1n+1n+1...