这几天做了些树状dp的题目，现在总结i一下。
树的最大独立集：
复制代码
1这类题目大概是碰到最多的。独立集是指，一个图中的子点集，集合中的点都不相邻。题目一般会描述成给你一个树状关系，然后下属和上司不能同时出现，选出最多的人参加活动。递推式：dp[root][1]=Σdp[son][0],dp[root][0]=Σmax(dp[son][1],dp[son][0])+1(0表示该节点不选，1表示选择),如果节点带权值则最后+1改为+上权值。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102#include<cstdio> #include<map> #include<string> #include<iostream> #include<vector> #include<algorithm> #include<cstring> using namespace std; const int maxn=300; string temp,namef,names,out;///用一个map存储该节点的数字代号，v[i][j]表示第i个节点的第j个儿子 int n,cnt,judge[maxn][2]; int dp(int st,int t,vector<int> edge[]){ if(!edge[st].size()){ if(t==0) return 0; else return 1; } int ans=0; if(t==1){ for(int i=0;i<edge[st].size();i++){ ans+=dp(edge[st][i],0,edge); if(judge[edge[st][i]][0]) judge[st][1]=true; } return ans+1; } if(t==0){ for(int i=0;i<edge[st].size();i++){ int m1=dp(edge[st][i],0,edge); int m2=dp(edge[st][i],1,edge); if(m1>m2){ if(judge[edge[st][i]][0]) judge[st][0]=true; ans+=m1; } else if(m2>m1){ if(judge[edge[st][i]][1]) judge[st][0]=true; ans+=m2; } else if(m1==m2){ judge[st][0]=true; ans+=m1; } //ans+=max(m1,m2); } return ans; } } int main(){ //freopen("out.txt", "w", stdout);//参数分别是，输出的文件的文件名，w是write（写），stdout（输出）， while(scanf("%d",&n)!=EOF){ if(n==0) break; map<string,int> id; vector<int> edge[maxn]; memset(judge,0,sizeof(judge)); cnt=1; cin>>temp; for(int i=0;i<n-1;i++){ cin>>names; cin>>namef; if(!(id[namef]>=1&&id[namef]<=n)){ id[namef]=cnt++; } if(!(id[names]>=1&&id[names]<=n)){ id[names]=cnt++; } int u=id[namef]; int v=id[names]; edge[u].push_back(v); } // int st=id[temp]; int ans1=dp(st,0,edge); int ans2=dp(st,1,edge); //cout<<1<<endl; //cout<<ans1<<" "<<ans2<<endl; if(ans1 == ans2) printf("%d Non", ans1);//判断谁在数更大 else if(ans1 > ans2) printf("%d %sn", ans1, judge[st][0] ? "No" : "Yes"); else printf("%d %sn", ans2, judge[st][1] ? "No" : "Yes"); /*if(ans1==ans2) out="No"; else if(ans1<ans2){ if(judge[1][1]) out="No"; else out="Yes"; } else{ if(judge[1][0]) out="No"; else out="Yes"; }*/ //printf("%d ",max(ans1,ans2)); //cout<<out<<endl; } return 0; }
树的重心：
复制代码
1给出一棵树，如果删掉某个点后所产生的最大子树是最小的，则这个点为树的重心，(详细解释参考刘汝佳紫书）。思路：首先从某个点开始dfs（因为是无根树，那么这个开始点即为转化过后的有根树的根节点）。dfs根节点的每个子节点则dp[root]=Σdp[j]+1，(dp[r]表示r节点所还有的节点个数），删除掉root后，产生的子树最大为dp_max[j],然后再用它与n-dp[root]比较得出最大值即为该点的“平衡值”。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#include<cstdio> #include<vector> #include<iostream> #include<cstring> #include<algorithm> #define inf 0x3f3f3f3f using namespace std; const int maxn=2e4+50; int t,n,u,v,max_balance,max_node; vector<int> vec[maxn]; int dfs(int root,int fa){ int sum,t,bx; sum=1;///记录的是当前节点往下所包含的节点数 bx=0;///当前节点的子节点的最大平衡值 for(int i=0;i<vec[root].size();i++){ int son=vec[root][i]; if(son==fa) continue; t=dfs(son,root); bx=max(bx,t); sum+=t; } bx=max(n-sum,bx); if(bx<max_balance||(bx==max_balance&&root>max_node)){ max_balance=bx; max_node=root; } return sum; } int main(){ while(scanf("%d",&t)!=EOF){ for(int i=0;i<t;i++){ memset(vec,0,sizeof(vec)); max_balance=inf; scanf("%d",&n); for(int j=0;j<n-1;j++){ scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); } dfs(1,-1); printf("%d %dn",max_node,max_balance); } } return 0; }/*poj1655*/
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; int read() { char ch;int s=0,f=1; ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-') f*=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-48; ch=getchar(); } return s*f; } struct node { int y,nxt; }e[50000*2+10]; int head[50005],ans[50005],top,cnt; int size[50005],nm,mx[50005]; int n; void add(int x,int y)///链式前向星存图，比较奇怪的是如果换成ec的节点方式就会TLE { cnt++; e[cnt].nxt=head[x],e[cnt].y=y; head[x]=cnt; } void getson(int x,int fa) { size[x]=1; for(int i=head[x];i;i=e[i].nxt) { int v=e[i].y; if(v==fa) continue; getson(v,x); size[x]+=size[v]; mx[x]=max(mx[x],size[v]); } mx[x]=max(mx[x],n-size[x]); if(mx[x]<nm){ nm=mx[x]; top=0; ans[top++]=x; } else if(nm==mx[x]) ans[top++]=x; } int main() { n=read(); for(int i=1;i<n;i++) { int u,v; u=read(),v=read(); add(u,v); add(v,u); } nm=100000000; getson(1,0); // printf("%d",top); sort(ans,ans+top); for(int i=0;i<top;i++) printf("%d ",ans[i]); return 0; }/*poj3107*/
树的最长路：
复制代码
1给出一棵树，求这棵树的最长路径。这道题有两种思路 1）任意搜索一个节点的最远路，然后再从这次的最远节点出发搜索最远路。2）从每一个节点出发搜索出它的最长路径和次长路径，最终最长路径就是两者之和，最后取所有节点的最大值。不过思路2有个地方需要注意的是：一个节点的最长路，应是子节点出发的最长路和父节点出发的最长路取最大值（推荐思路2实现因为思路2还可以求出图上任意节点的最远路）
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include<cstdio> #include<cstring> #include<iostream> #include<vector> using namespace std; const int maxn=1e5+50; int n,u,v,dp[maxn],maxs,temp; vector<int> vec[maxn]; void dfs(int root,int fa,int dist){ dp[root]=dist;///当前节点到 1号点或temp的距离 for(int i=0;i<vec[root].size();i++){ int son=vec[root][i]; if(son==fa) continue; dfs(son,root,dist+1); } } int main(){ scanf("%d",&n); maxs=-1; for(int i=0;i<n-1;i++){ scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); } dfs(1,-1,0); for(int i=1;i<=n;i++){ if(dp[i]>maxs){ temp=i;///存储端点，这是下次出发找最长路的起点 maxs=dp[i]; } } maxs=-1; memset(dp,0,sizeof(dp)); dfs(temp,-1,0); for(int i=1;i<=n;i++){ if(dp[i]>maxs){ maxs=dp[i]; } } printf("%dn",maxs); } /*hihocode 1050 思路1实现*/
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn=1e4+50; int n,u,v,weight,dp_max[maxn],dp_smax[maxn],smaxid[maxn],maxid[maxn]; struct edge{ int weight,v; edge(int ww,int vv):weight(ww),v(vv){ } }; vector<edge> vec[maxn]; void dfs_leaves(int root,int fa){///搜索得出子节点的最长路和次长路 dp_max[root]=dp_smax[root]=0; for(int i=0;i<vec[root].size();i++){ edge son=vec[root][i]; if(son.v==fa) continue; dfs_leaves(son.v,root); if(dp_max[son.v]+son.weight>dp_smax[root]){ dp_smax[root]=dp_max[son.v]+son.weight; smaxid[root]=son.v; } if(dp_smax[root]>dp_max[root]){ swap(maxid[root],smaxid[root]); swap(dp_max[root],dp_smax[root]); } } } void dfs_father(int root,int fa){///搜索得出父节点出发的最长路 次长路 for(int i=0;i<vec[root].size();i++){ edge son=vec[root][i]; if(son.v==fa) continue; if(son.v==maxid[root]){ if(dp_smax[root]+son.weight>dp_smax[son.v]){ dp_smax[son.v]=dp_smax[root]+son.weight; smaxid[son.v]=root; if(dp_smax[son.v]>dp_max[son.v]){ swap(dp_smax[son.v],dp_max[son.v]); swap(maxid[son.v],smaxid[son.v]); } } } else{ if(dp_max[root]+son.weight>dp_smax[son.v]){ dp_smax[son.v]=dp_max[root]+son.weight; smaxid[son.v]=root; if(dp_smax[son.v]>dp_max[son.v]){ swap(dp_smax[son.v],dp_max[son.v]); swap(maxid[son.v],smaxid[son.v]); } } } dfs_father(son.v,root);///因为先前有数据存储在dp中，所以先把前面数据处理完再递归 } } int main(){ while(scanf("%d",&n)!=EOF){ //memset(dp_max,0,sizeof(dp_max)); memset(vec,0,sizeof(vec)); for(int i=2;i<=n;i++){ scanf("%d%d",&v,&weight); vec[i].push_back(edge(weight,v)); vec[v].push_back(edge(weight,i)); } dfs_leaves(1,-1); dfs_father(1,-1); for(int i=1;i<=n;i++) printf("%dn",dp_max[i]); } return 0; }/*hdu2196 思路2实现*/
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> using namespace std; const int maxn=1e4+50; int u,v,weight,dp_max[maxn],dp_smax[maxn],maxid[maxn],smaxid[maxn],max_node,max_edge; struct edge{ int weight,to; edge(int ww,int tt):weight(ww),to(tt){ } }; vector<edge> vec[maxn]; void dfs_leaves(int root,int fa){ for(int i=0;i<vec[root].size();i++){ edge son=vec[root][i]; if(son.to==fa) continue; dfs_leaves(son.to,root); if(dp_max[son.to]+son.weight>dp_smax[root]){ dp_smax[root]=dp_max[son.to]+son.weight; smaxid[root]=son.to; if(dp_smax[root]>dp_max[root]){ swap(dp_smax[root],dp_max[root]); swap(maxid[root],smaxid[root]); } } } } void dfs_father(int root,int fa){ for(int i=0;i<vec[root].size();i++){ edge son=vec[root][i]; if(son.to==fa) continue; if(son.to==maxid[root]){ if(dp_smax[root]+son.weight>dp_smax[son.to]){ dp_smax[son.to]=dp_smax[root]+son.weight; smaxid[son.to]=root; if(dp_smax[son.to]>dp_max[son.to]){ swap(dp_smax[son.to],dp_max[son.to]); swap(smaxid[son.to],maxid[son.to]); } } } dfs_father(son.to,root); } } int main(){ memset(dp_max,0,sizeof(dp_max)); memset(dp_smax,0,sizeof(dp_smax)); memset(vec,0,sizeof(vec)); max_node=max_edge=0; while(scanf("%d%d%d",&u,&v,&weight)==3){ vec[u].push_back(edge(weight,v)); vec[v].push_back(edge(weight,u)); max_node=max(max_node,max(u,v)); } dfs_leaves(1,-1); dfs_father(1,-1); for(int i=1;i<=max_node;i++){ max_edge=max(max_edge,dp_max[i]+dp_smax[i]); } printf("%dn",max_edge);/*poj2631*/ }
最后
以上就是年轻音响最近收集整理的关于树上的dp总结的全部内容，更多相关树上内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复