首页 > [USACO 2008 Jan G]Cell Phone Network
头像 瑜画
发表于 2020-08-08 10:54:18
该题是点的最小覆盖集问题。题意:求覆盖一个树所有的点,需要覆盖最小的次数,覆盖一个点需要耗费一次次数,覆盖完以后,那么相邻的点也被覆盖。 对于无向树,直接随便找一个结点作为根,然后把整棵树支起来,就有了根和叶子!需要一点想象力,反正无向树怎么旋转都可以。那么寻找当前点的状态,如果一个树都被覆盖,那么 展开全文
头像 在刷题的单身狗很开心
发表于 2023-10-20 22:10:44
本题是点的最小覆盖集问题,是一个树形dp问题。 对于某一个节点来说他能通信来自于他父亲以及他儿子节点以及他自身。那么dp[n][3]表示某个节点三这种情况下的最小值。 0:靠父亲。 1:靠自己。 2:靠儿子。 那么对于靠自己和靠父亲来说很简单的能写出状态转移方程: 展开全文
头像 cboy__
发表于 2020-08-17 19:28:43
题意 • 给你一棵无向树,问你最少用多少个点可以覆盖掉所有其他的点。• (一个点被盖,它自己和与它相邻的点都算被覆盖) 思路 最小的点覆盖确定三种状态注意边界情况,设立哨兵 or 特判 0:覆盖u, 1:被son覆盖 (有点复杂:至少被一个v覆盖)根据贡献来,来,差值从小到大排序排序后, 展开全文
头像 Zhuwanxing
发表于 2021-04-26 22:37:52
树的最小支配集问题 题目大意:思路:对于任意一个点,只有三种被覆盖的情况1.被自己覆盖2.被自己的子节点覆盖3.被自己的父节点覆盖故很容易推出状态表示dp[i][j]:以i为根的子树的全部节点被覆盖且i节点的覆盖状态为j的所有方案的节点最小值(其中j = 0表示被自己覆盖,j = 1表示被儿子覆盖, 展开全文
头像 空白link
发表于 2020-08-09 12:07:55
NC24953*题目描述 *Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires hi 展开全文
头像 回归梦想
发表于 2020-08-28 10:00:23
来源:牛客网 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld 题目描述 Farmer John has decided to give each of his cows a cell phone in 展开全文
头像 Z_L_G
发表于 2025-05-16 10:56:03
最小支配集 选择一个点,可以覆盖相邻的点,覆盖所有点所需最小选点 题意 给定一颗n个结点的树,求最小支配集 思路 考虑每一个点,他可能被支配的方式有:被父亲支配,选自己,被儿子支配,维护一个二维dp数组记录点和状态: 自己: 父亲: 儿子: 对于自己和父亲,状态方程很显然可以推出,对于 展开全文
头像 下次一定中奖
发表于 2020-08-16 21:44:40
原题链接:https://ac.nowcoder.com/acm/problem/24953 题目大意: 求覆盖一个树所有的点,需要覆盖最小的次数,覆盖一个点需要耗费一次次数,覆盖完以后,那么相邻的点也被覆盖。 解题思路: 每一个点有三种状态:  1.自己覆盖自己  2.儿子节点覆盖自己  展开全文
头像 Ray.C.L
发表于 2020-08-10 22:59:50
思路:要选最少的点去覆盖完整个树,根据覆盖关系我们有3个状态。 1.dp[i][0]表示以i为根节点,选i覆盖完所有子树的最小值 2.dp[i][1]表示不选i,i节点被子节点覆盖 3.dp[i][2]表示不选i节点,i节点被父亲节点覆盖。 对于第一种状态,i选以后他的子节点的覆盖关系就是3种取最小 展开全文
头像 savage
发表于 2019-08-14 16:38:45
题目描述 Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him t 展开全文