概述
这几天做了些树状dp的题目，现在总结i一下。
树的最大独立集：
这类题目大概是碰到最多的。独立集是指，一个图中的子点集，集合中的点都不相邻。题目一般会描述成给你一个树状关系，然后下属和上司不能同时出现，选出最多的人参加活动。递推式：dp[root][1]=Σdp[son][0],dp[root][0]=Σmax(dp[son][1],dp[son][0])+1(0表示该节点不选，1表示选择),如果节点带权值则最后+1改为+上权值。
#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;
}
树的重心：
给出一棵树，如果删掉某个点后所产生的最大子树是最小的，则这个点为树的重心，(详细解释参考刘汝佳紫书）。思路：首先从某个点开始dfs（因为是无根树，那么这个开始点即为转化过后的有根树的根节点）。dfs根节点的每个子节点则dp[root]=Σdp[j]+1，(dp[r]表示r节点所还有的节点个数），删除掉root后，产生的子树最大为dp_max[j],然后再用它与n-dp[root]比较得出最大值即为该点的“平衡值”。
#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*/#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）任意搜索一个节点的最远路，然后再从这次的最远节点出发搜索最远路。2）从每一个节点出发搜索出它的最长路径和次长路径，最终最长路径就是两者之和，最后取所有节点的最大值。不过思路2有个地方需要注意的是：一个节点的最长路，应是子节点出发的最长路和父节点出发的最长路取最大值（推荐思路2实现因为思路2还可以求出图上任意节点的最远路）
#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实现*/#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实现*/#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总结的全部内容，希望文章能够帮你解决树上的dp总结所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复