- 1、没有上司的舞会（最大独立集问题）
- 补充：LeetCode 337 打家劫舍 III
- 2、树的最长路径 / 树的直径
- 3、树的中心
- 4、数字转换
- 5、二叉苹果树（有依赖背包的特殊情况）
- 6、战略游戏（与第1题相反）
- 7、皇宫看守
ACWing 285
集合
f(u,0)、f(u,1)
f(u,0)：所有从以u为根的子树中选择的方案，选择并且不选u这个点的方案
f(u,1)：所有从以u为根的子树中选择的方案，选择并且选u这个点的方案
集合划分
状态计算
f(u, 0) = sum(max(f(si, 0), f(si, 1)))
f(u, 1) = sum(f(si, 0))（因为选了根结点，子结点就不可以选择）
#include补充：LeetCode 337 打家劫舍 III#include #include using namespace std; const int N = 6010; int n; int happy[N]; int h[N], e[N], ne[N], idx; int f[N][2]; bool has_father[N]; // 判断每个结点是否有父结点 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs(int u) { f[u][1] = happy[u]; // 选择u这个结点 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += max(f[j][0], f[j][1]); f[u][1] += f[j][0]; } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]); memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i ++ ) //读入n-1条边 { int a, b; scanf("%d%d", &a, &b); has_father[a] = true; add(b, a); } // 因为这个题没有告诉我们根结点是谁，所以需要自己寻找 int root = 1; while (has_father[root]) root ++ ; dfs(root); printf("%dn", max(f[root][0], f[root][1])); return 0; }
题目链接
这个题与上一题一模一样，但是要注意代码的实现。
2、树的最长路径 / 树的直径ACwing 1072
最经典的问题是不带权值的树的直径，也就是边数最长的两个结点之间的距离。
常用做法是：
1. 任取一点作为起点，找到距离该点最远的一个点u。然后再BFS （能使用BFS就不使用DFS，因为考试C++栈仅有1M大小，如果DFS层数过多，会爆栈） 2. 再找到距离u最远的一个点v。然后继续BFS。 3. 那么u和v之间的路径就是一条最长直径。
结论：任取树中一个点a，找到距离a最远的点u，则u一定是某条直径上的端点。如果证明了u是某条直径的端点，从u开始求出来的距离u最远的点v，u和v之间的路径一定就是树最长路径 / 直径。
证明：
反证法：若距离任意一点a的最远点u不是任意一条直径上的某一个端点，假设树的真正直径为b与c之间的连线。下面分情况讨论：
- 若连线au与连线bc之间没有交点。在au和bc上各取一个点分别为x与y，由于树是连通的，即a、u、b、c四个点之间可以相互连通，那么x与y之间也可以相互连通，所以就有如下图。
又由我们之前的假设可知： ① ≥ ② + ③ ①ge②+③ ①≥②+③，即 ① + ② ≥ ① − ② ≥ ③ ①+②ge①-②ge③ ①+②≥①−②≥③，所以路径byxu的长度大于等于路径bc的长度，与假设矛盾；
- 若连线au与连线bc之间有交点。同理， ① ≥ ② ①ge② ①≥②，那么路径bxu的长度大于等于路径bc的长度，与假设矛盾。
证毕。
现在讨论扩展之后，即加上权值之后的树的最长路径问题。
按照定义，我们要求出树的所有直径，然后在这所有直径中取一个最小值即可。从集合角度思考，需要先将这些直接分成若干类，在这每一类中去寻找一个最大值，最后在所有最大之中取一个最大值即可。
路径分类
任取一个点，我们将其作为根结点，对于每一条直径，我们将其归类到这条路径中最高的点的这一类中。于是我们可以以每个点来分类，所以集合划分就是所有路径上最高的点是该点的路径的集合。
如何求出所有挂到该点上的所有路径长度的最大值呢？可以先将该结点的所有子结点往下走的所有路径长度最大值先求出来。对于挂在该点上的所有路径可分为两大类：
- 一直往下走，直到走到叶子结点。它的路径最大长度就是枚举每一个子结点往下走的路径的最大距离，然后加上到根结点的1即可；
- 路径穿过了该结点，往左子树或者右子树下面走。该结点的路径最大长度为从这两个方向下去的所有最长路径长度的最长的一条路径和第二长的一条路径的和。所以可以先求出每一个子结点的路径最大值，再将所有的最大值中取一个最大值即可。
题解参考
#include3、树的中心#include #include using namespace std; const int N = 1e4 + 10, M = N << 1; //初始不确定树的拓扑结构，因此要建立双向边 int n; int h[N], e[M], w[M], ne[M], idx; int f1[N], f2[N], res; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } void dfs(int u, int father) //father表示u的父节点,因为该图为无向图,并且迭代过程中不能回到父节点,所以要特殊标记 { f1[u] = f2[u] = 0; //以节点u为根的子树中，从子树某个节点到u的最长路为f1，次长路径为f2 for (int i = h[u]; i != -1; i = ne[i]) // 遍历邻边 { int j = e[i]; if (j == father) continue; //如果是父节点， 则不走 dfs(j, u); if (f1[j] + w[i] >= f1[u]) f2[u] = f1[u], f1[u] = f1[j] + w[i]; // 最长路转移 else if (f1[j] + w[i] > f2[u]) f2[u] = f1[j] + w[i]; // 次长路转移 } res = max(res, f1[u] + f2[u]); } int main() { cin >> n; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i ++ ) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } // 任取一个结点作为根结点，这样整棵树的拓扑结构被唯一确定下来了：这里取第1个结点 // 为了避免dfs往上走（会死循环），传给它一个父结点，根结点的父结点为-1 dfs(1, -1); cout << res << endl; return 0; }
ACwing 1073
树的中心，即这个结点到其它结点的距离最小，类似于圆心。可以分别求出每个结点到其它结点的最远距离，在所有的最远距离中取一个最小值。那么如何求出每个结点到其它结点的最远距离呢？
分类方法
对于每个结点，它到其它结点的最远距离分为两大类（这里以2结点为例）：
- 往子结点走的所有结点最远距离：按上一题的路径分类1中的方法来求；
- 往父结点走的所有结点最远距离：这里分为两步，即：2 → 1 的距离 + 从1出发的距离
- 从2 → 1的距离，就是2 → 1上的权值，所有路径都一样；
- 从1出发
- 继续往父结点走的最大值1 → 7 → ...
- 往子结点走的最大值
- 若不经过当前结点2，返回距离的最大值
- 若经过当前结点2，返回距离的第二大值，即次大值（因为不能经过2）
#include4、数字转换#include #include using namespace std; const int N = 10010, M = N * 2, INF = 0x3f3f3f3f; int n; int h[N], w[M], e[M], ne[M], idx; int d1[N], d2[N], up[N]; // 分别表示往下走的最长路径，次长路径，往上走的最长路径 int p1[N], p2[N]; // 记录当前结点往下走的最长路径和次长路径是从哪一个结点往下走的 void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int dfs_d(int u, int father) // 返回从这个结点往下走的最长距离 { if (h[u] == -1) // 如果是叶子结点 return 0; d1[u] = d2[u] = -INF; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j == father) // 如果它是往上走 continue; int d = dfs_d(j, u) + w[i]; if (d >= d1[u]) { d2[u] = d1[u], d1[u] = d; p2[u] = p1[u], p1[u] = j; } else if (d > d2[u]) d2[u] = d, p2[u] = j; } if (d1[u] == -INF) // 说明从未更新过，即它为一个叶子结点 d1[u] = d2[u] = 0; return d1[u]; } //用父节点更新一下子节点向上的最长路径 void dfs_u(int u, int father) { for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (j == father) continue; if (p1[u] == j) // 如果最长路径是从子结点过来的，最大值只能从次大值来更新 up[j] = max(up[u], d2[u]) + w[i]; else // 如果不是从子节点过来的 up[j] = max(up[u], d1[u]) + w[i]; dfs_u(j, u); } } int main() { cin >> n; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } // 随便从一个结点开始往下走的最长距离，这里选择 1 结点 // -1 为其父结点 dfs_d(1, -1); // 每个结点往上走的最长路径，同样是以任意一个结点为根节点来求解 dfs_u(1, -1); int res = INF; for (int i = 1; i <= n; i++) res = min(res, max(d1[i], up[i])); // 每个点的最大距离分为往上走和往下走最大距离 printf("%dn", res); return 0; }
ACwing 1075
因为每个数的约数之和是固定的，所以我们在每个数和其约数之间建立一条边，且约数之和为父结点，即每个点最多只有一个父结点，那么在所有这些可以相互变换的点之间连一条边的话，这1 ~ n之间的树就会构成一堆树（森林）的形式，这时候问题就转换成了：在这些所有的树里面找到一条长度最长的路径，且不能走回头路（不能包含相同的点）。
如果快速求出每个数的约数？枚举1 ~ n之间每个数的倍数有哪些。
for (int i = 1; i <= n; i ++ ) for (int j = 2; j <= n / i; j ++ ) // j从2开始，因为不能包含相同的点；这里不能写成 j*i <= n，因为 j*i 可能溢出
#include5、二叉苹果树（有依赖背包的特殊情况）#include #include using namespace std; const int N = 50010; int n; int e[N], ne[N], h[N], idx; int sum[N]; // 所有数的约数之和 bool st[N]; // 存储该结点是否是树根 int ans; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } int dfs(int u) { int d1 = 0, d2 = 0; // d1是最长距离，d2是次长距离 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; int d = dfs(j) + 1; if (d >= d1) // 更新最长距离和次长距离 d2 = d1, d1 = d; else if (d > d2) d2 = d; } ans = max(ans, d1 + d2); return d1; } int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 2; j <= n / i; j++) // 这里不能写成 j*i <= n，因为 j*i 可能溢出 sum[i * j] += i; memset(h, -1, sizeof h); for (int i = 2; i <= n; i++) // 1 的所有约数之和是0，变换过程中不能出现0 if (i > sum[i]) // i的约数之和小于i { add(sum[i], i); st[i] = true; // i 不是树根，有父节点 } for (int i = 1; i <= n; i++) if (!st[i]) // 因为有多棵树，只枚举没有被标记过的点（即树根） dfs(i); // 这里不传入father是因为有向边不会枚举到父节点 cout << ans << endl; return 0; }
ACwing 1074
因为每个最后要保留的路径一定要与根结点相连，所以对于任意一个非根结点，要保留它，就必须保留它的父节点，所以存在一个依赖关系。对于每个点看成一个体积是1的物品，与其父结点连线上的权值，看成是这个点的价值，最终可以保留的边的个数Q看成背包容量，这样这个题就转换成了有依赖的背包问题了。
集合
f[i,j]：表示在以i为根的子树里面，选择j条边的最大价值
集合划分
每棵子树看成分组背包中的一组（本题只有两棵子树），对于每棵子树si，选择k (0 <= k <= j-1，因为要保留子树和父结点的相连的边)条边的价值为f(si, k)，体积为k。
#include6、战略游戏（与第1题相反）#include #include using namespace std; const int N = 110, M = N * 2; // 无向图 int n, m; int h[N], e[M], ne[M], w[M], idx; int f[N][N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } void dfs(int u, int father) { for (int i = h[u]; i != -1; i = ne[i]) { if (e[i] == father) continue; dfs(e[i], u); // 分组背包 for (int j = m; j >= 0; j--) // 枚举体积 for (int k = 0; k < j; k++) // 枚举每组物品 f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]); } } int main() { cin >> n >> m; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } // 1 是根结点 // 因为是无向树，所以要传入father = -1 dfs(1, -1); cout << f[1][m] << endl; return 0; }
ACwing 323
- 没有上司的舞会（独立集问题）：每条边上最多选择一个点。最大权值。
- 战略游戏：每条边上至少选择一个点。最小权值。
集合
f[i,j](j = 0 or 1)：所有在以i为根的子树中选择，且点i的状态是j的所有选法的权值（士兵数量）的最小值
集合划分
- f[i,0]：所有在以i为根的子树中选择，并且不选择i的所有选法的最大权值。举例如图，以i为根的树的权值最小，就必须使以i根的三棵子树权值最小（三棵子树是独立的），因为每条边上至少选择一个点的前提，且i未选择，所以三棵子树的状态为f[s1,1]、f[s2,1]、f[s3,1]。
所以f[i,0] = min(f[s1,1] + f[s2,1] + ... ) - f[i,1]：所有以i为根的子树中选择，并且选择i的所有选法的最大权值。对于子树si可选可不选，所以应该在可选可不选的选法中取得一个最小值。所以f[i,1] = min(min(f[s1,0], f[s1,1]) + min(f[s2,0], f[s2,1]) + ... )
#include7、皇宫看守#include #include using namespace std; const int N = 1510; int n; int h[N], e[N], ne[N], idx; int f[N][2]; bool st[N]; // 记录谁是根结点 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u) { f[u][0] = 0; f[u][1] = 1; // 当前结点放置 for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += f[j][1]; // 当前结点不选择 f[u][1] += min(f[j][0], f[j][1]); } } int main() { while (scanf("%d", &n) != -1) // scanf 没有读到元素返回-1，读到元素饭会元素个数 { memset(h, -1, sizeof h); memset(st, 0, sizeof st); idx = 0; for (int i = 0; i < n; i++) { int id, cnt; scanf("%d:(%d)", &id, &cnt); while (cnt--) { int ver; scanf("%d", &ver); add(id, ver); st[ver] = true; } } int root = 0; while (st[root]) root++; dfs(root); printf("%dn", min(f[root][0], f[root][1])); } return 0; }
ACwing 1077
- 没有上司的舞会（独立集问题）：每条边上最多选择一个点。最大权值。
- 战略游戏（观察到所有的边）：每条边上至少选择一个点。最小权值。
- 皇宫看守（观察到所有的点）：某一点以及与这个点相连的所有邻点上边至少选择一个点。
在战略游戏中，因为只要求观察到所有的边，所以我们只需要考虑父结点放不放置即可，但是这个题要求观察到所有的点，所以会出现下面三种情况：
- 父节点 放置 哨兵，所有子节点都 可放可不放 哨兵；
- 父节点 不放 哨兵，但是他至少有一个 子节点 放置哨兵，观察住了他；
- 父节点 不放 哨兵，但 父节点 的 父节点 放置哨兵观察，则 子节点 可放可不放 哨兵。
集合划分
式子中的j代表所有子结点。
- f[i,0]：点i没有放警卫，能被父结点看到的所有摆放方案的最小花费。i是被他父结点看住的，那他的子结点要么自己看自己，要么被自己的子结点看到。故： f [ i , 0 ] = ∑ m i n ( f [ j , 1 ] , f [ j , 2 ] ) f[i,0]=sum min(f[j,1], f[j,2]) f[i,0]=∑min(f[j,1],f[j,2])；
- f[i,1]：点i没有放警卫，能被子结点看到的所有摆放方案的最小花费。枚举哪一个子结点看到了它，在所有的子结点中取一个最小值即可。假设枚举到子结点k看到了父结点i， f [ i , 1 ] = m i n ( f [ k , 2 ] + ∑ j ! = k m i n ( f [ j , 1 ] , f [ j , 2 ] ) ) f[i,1] = min(f[k,2]+ sum_{j != k}min(f[j,1], f[j,2])) f[i,1]=min(f[k,2]+∑j!=kmin(f[j,1],f[j,2]))，这个公式表示第k个结点一定要安排一个守卫，其余子结点可以安排也可以不安排守卫。注意后面一部分最小值已经记录到 f [ i , 0 ] f[i,0] f[i,0]中了，可以直接减去 f [ i , 0 ] − m i n ( f [ k , 1 ] , f [ k , 2 ] ) f[i, 0] - min(f[k,1],f[k,2]) f[i,0]−min(f[k,1],f[k,2]) 即可；
- f[i,2]：点i上安排警卫的所有摆放方案的最小花费。 i是被自己看到的，那他的子结点可以被父结点看到，可以自己看自己，也可以被自己的子结点看到，故 f [ i , 2 ] = ∑ m i n ( f [ j , 0 ] , f [ j , 1 ] , f [ j , 2 ] ) f[i,2]=sum min(f[j,0],f[j,1],f[j,2]) f[i,2]=∑min(f[j,0],f[j,1],f[j,2])。
#include#include #include using namespace std; const int N = 1510; int n; int e[N], ne[N], w[N], h[N], idx; int f[N][3]; bool st[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u) { f[u][2] = w[u]; // 若要布置守卫，该结点花费w[u] for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += min(f[j][1], f[j][2]); f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]); // 三个的最小值 } f[u][1] = 1e9; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2])); } } int main() { cin >> n; memset(h, -1, sizeof h); for (int i = 1; i <= n; i++) { int id, cost, cnt; // 编号、花费、所有子节点信息 cin >> id >> cost >> cnt; w[id] = cost; while (cnt--) { int ver; cin >> ver; add(id, ver); // 添加一条当前结点指向子结点的信息 st[ver] = true; // 有父节点了，故不是根结点 } } int root = 1; while (st[root]) root++; dfs(root); cout << min(f[root][1], f[root][2]) << endl; // 根结点没有父结点，不可能被父节点看见 return 0; }
