锐客网

  1. 首页 > 睿知 > it技术 > >

树上dp|树的最小支配集和最小点覆盖

算法c++树上dpacm竞赛

【树上dp|树的最小支配集和最小点覆盖】最小支配集
定义1：对于图G=(V,E)来说，最小支配集指的是从V中取尽量少的点组成一个集合，使得对于V中剩余的点都与取出来的点有边相连。也就是说，设V‘是图G的一个支配集，则对于图中的任意一个顶点u，要么属于集合V’，要么与V‘中的顶点相邻。在V’中出去任何元素后V‘不再是支配集，则支配集是极小支配集。称G的所有支配集中顶点个数最少的支配集为最小支配集，最小支配集中顶点的个数称为支配数。
最小点覆盖
定义2：对于图G=(V,E)来说，最小点覆盖指的是从V中取尽量少的点组成一个集合，使得E中所有的边都与取出来的点相连。也就是说，设V‘是图G的一个顶点覆盖，则对于图中的任意一条边(u,v)，要么u属于集合V’，要么v属于集合V‘。在V‘中除去任何元素后V’不在是顶点覆盖，则V‘是极小顶点覆盖。称G的所有顶点覆盖中顶点个数最少的覆盖为最小点覆盖。
最大独立集
定义3：对于图G=(V,E)来说，最大独立集指的是从V中取尽量多的点组成一个集合，使得这些点之间没有边相连。也就是说，设V’是图G的一个独立集，则对于图中任意一条边(u,v)，u和v不能同时属于集合V'，甚至可以u和v都不属于集合V‘。在V’中添加任何不属于V‘元素后V’不再是独立集，则V‘是极大独立集。称G的所有顶点独立集中顶点个数最多的独立集为最大独立集。
Strategic game【树上DP】【树的最小点覆盖】
题解：不取父亲结点，那么必须取儿子节点，这样才能保证父亲和儿子的连边会被覆盖；
取父亲结点，那么儿子节点可取 可不取；
dp[ u ] [ 0 ] += dp [ v ] [ 1 ] ;
dp [ u ] [ 1 ] += min( dp [ v ] [ 1 ] , dp [ v ] [ 0 ] ) ;

#include using namespace std; #define sc(x) scanf("%d",&x) #define sl(x) scanf("%lld",&x) #define ll long long #define pb push_back typedef pairPII; const int Max=2e5+5; const ll INF=1e15+5; const ll mod=1e9+7; int h[Max],a[Max]; int dp[Max][3]; vectormp[Max]; void dfs(int fa,int x){ int tot=0,len=mp[x].size(); dp[x][1]=1; for(int i=0; i

[USACO 2008 Jan G]Cell Phone Network【树上DP】【树的最小支配集】
题意：
John想让他的所有牛用上手机以便相互交流，他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地能收到信号。给你N-1个草地(A，B)的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。
思路：
树的最小支配集。
定义：
dp[i][0]为这个点本身有观测站，
dp[i][1]为这个点没有观测站，但是父亲有，
dp[i][2]为这个点没有观测站，但是儿子有，
那么结果就是min(dp[i][0],dp[i][2])。
转移：
dp[i][0]=∑min(dp[j][0],dp[j][1],dp[j][2])
dp[i][1]=∑min(dp[j][0],dp[j][2])
dp[i][2]=∑min(dp[j][0],dp[j][2])?min(max(dp[j][0],dp[j][2])?dp[j][2])
注意对于dp[i][2]，我们要保证子节点至少有一个有观测站，所以如果选的全部是dp[j][2]，那么一定要有一个儿子将dp[j][2]替换成dp[j][0]，多出来的部分就是dp[j][0]+dp[j][2]，取最小的部分，最后加上。
#include using namespace std; #define sc(x) scanf("%d",&x) #define sl(x) scanf("%lld",&x) #define ll long long #define pb push_back typedef pairPII; const int Max=2e5+5; const ll INF=1e15+5; const ll mod=1e9+7; int h[Max],a[Max]; int dp[Max][3]; vectormp[Max]; void dfs(int fa,int x){ int tot=0,len=mp[x].size(); dp[x][0]=1; for(int i=0; idp[v][1]&&tot


    推荐阅读


    上一篇：牛客竞赛|牛客挑战赛59 B 游戏【dp】

    下一篇：ccpc|The 2021 CCPC Weihai Onsite E. CHASE!