首页 > 代码库 > csu 2014 summer training day 3 简单树形dp
csu 2014 summer training day 3 简单树形dp
FZU 2157
题意：树上的节点可以打上0或1的标记，树的权值由两部分呢组成，点权和边权，有00、01、10、11四种组合的边权，
问最小权值和。以1节点为树根
分析:dp[x][0]表示x标记0后的最小的权值，dp[x][1]同理
那么每次可以计算dp[x][0],dp[x][1]；
例如dp[x][1]=min(dp[son][0]+lab[0][1]+val[1],dp[son][1]+bal[1][1]+val[1]);
具体看代码。
用bfs写的分层，深搜代码更简洁
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <vector> 5 #include <map> 6 #include <string> 7 #include <queue> 8 #define LL long long 9 #define maxn 20100010 using namespace std;11 //map存储标号12 //边读边记录边的关系13 //bfs分层记录每层节点14 //从底层向上层dp15 int la[maxn][2];16 int bel[maxn][2][2];17 vector<int> G[maxn];18 vector<int> Ceil[maxn];19 int n,cnum;//点数，分层数20 void init(){21 for(int i=0;i<maxn;i++) G[i].clear();22 for(int i=0;i<maxn;i++) Ceil[i].clear();23 cnum=0;24 return ;25 }26 typedef pair<int,int>PAIR;27 bool vis[maxn];28 void Bfs(){29 queue<PAIR> Q ;30 Q.push(make_pair(1,1));31 memset(vis,0,sizeof(vis));32 vis[1]=true;33 while(!Q.empty()){34 PAIR New=Q.front();35 Q.pop();36 int u=New.first;37 int st=New.second;38 Ceil[st].push_back(u);39 cnum=max(cnum,st);40 for(int i=0;i<G[u].size();i++){41 int v=G[u][i];42 if (vis[v]) continue;43 Q.push(make_pair(v,st+1));44 vis[v]=true;45 }46 }47 return;48 }49 LL dp[maxn][2];//0表示不选择i节点，1表示选择i节点50 void solve(){51 memset(dp,0,sizeof(dp));52 for(int i=0;i<Ceil[cnum].size();i++){53 int u=Ceil[cnum][i];54 dp[u][0]=(LL)la[u][0];dp[u][1]=(LL)la[u][1];55 }56 for(int i=cnum-1;i>=1;i--){57 for(int j=0;j<Ceil[i].size();j++){58 int u=Ceil[i][j];59 for(int k=0;k<G[u].size();k++){60 int v=G[u][k];61 dp[u][0]+=min(dp[v][0]+bel[v][0][0],dp[v][1]+bel[v][0][1]);62 dp[u][1]+=min(dp[v][0]+bel[v][1][0],dp[v][1]+bel[v][1][1]);63 }64 dp[u][1]+=(LL)la[u][1];65 dp[u][0]+=(LL)la[u][0];66 // cout<<"u="<<u<<","<<"1:"<<dp[u][1]<<endl;67 // cout<<"u="<<u<<","<<"0:"<<dp[u][0]<<endl;68 }69 }70 printf("%I64d\n",min(dp[1][1],dp[1][0]));71 return ;72 }73 int t;74 int main(){75 scanf("%d",&t);76 while(t--){77 scanf("%d",&n);78 init();79 for(int i=1;i<=n;i++){80 scanf("%d",&la[i][0]);81 }82 for(int i=1;i<=n;i++){83 scanf("%d",&la[i][1]);84 }85 int u,v,a,b,c,d;86 for(int i=1;i<=n-1;i++){87 scanf("%d%d%d%d%d%d",&u,&v,&a,&b,&c,&d);88 bel[v][0][0]=a;89 bel[v][0][1]=b;90 bel[v][1][0]=c;91 bel[v][1][1]=d;92 G[u].push_back(v);93 }94 Bfs();//分层95 solve();96 }97 return 0;98 }
POJ 2342
题意：给定一颗boss树，父亲节点和孩子节点不能同时出现，问最多能选出多少节点
分析：dp[x][0]：x不出现，dp[x][1]:x出现
dp[u][0]+=max(dp[v][1],dp[v][0]);dp[u][1]+=dp[v][0];1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <vector> 5 #include <map> 6 #include <string> 7 #include <queue> 8 #define LL long long 9 #define maxn 20100010 using namespace std;11 //map存储标号12 //边读边记录边的关系13 //bfs分层记录每层节点14 //从底层向上层dp15 int la[maxn][2];16 int bel[maxn][2][2];17 vector<int> G[maxn];18 vector<int> Ceil[maxn];19 int n,cnum;//点数，分层数20 void init(){21 for(int i=0;i<maxn;i++) G[i].clear();22 for(int i=0;i<maxn;i++) Ceil[i].clear();23 cnum=0;24 return ;25 }26 typedef pair<int,int>PAIR;27 bool vis[maxn];28 void Bfs(){29 queue<PAIR> Q ;30 Q.push(make_pair(1,1));31 memset(vis,0,sizeof(vis));32 vis[1]=true;33 while(!Q.empty()){34 PAIR New=Q.front();35 Q.pop();36 int u=New.first;37 int st=New.second;38 Ceil[st].push_back(u);39 cnum=max(cnum,st);40 for(int i=0;i<G[u].size();i++){41 int v=G[u][i];42 if (vis[v]) continue;43 Q.push(make_pair(v,st+1));44 vis[v]=true;45 }46 }47 return;48 }49 LL dp[maxn][2];//0表示不选择i节点，1表示选择i节点50 void solve(){51 memset(dp,0,sizeof(dp));52 for(int i=0;i<Ceil[cnum].size();i++){53 int u=Ceil[cnum][i];54 dp[u][0]=(LL)la[u][0];dp[u][1]=(LL)la[u][1];55 }56 for(int i=cnum-1;i>=1;i--){57 for(int j=0;j<Ceil[i].size();j++){58 int u=Ceil[i][j];59 for(int k=0;k<G[u].size();k++){60 int v=G[u][k];61 dp[u][0]+=min(dp[v][0]+bel[v][0][0],dp[v][1]+bel[v][0][1]);62 dp[u][1]+=min(dp[v][0]+bel[v][1][0],dp[v][1]+bel[v][1][1]);63 }64 dp[u][1]+=(LL)la[u][1];65 dp[u][0]+=(LL)la[u][0];66 // cout<<"u="<<u<<","<<"1:"<<dp[u][1]<<endl;67 // cout<<"u="<<u<<","<<"0:"<<dp[u][0]<<endl;68 }69 }70 printf("%I64d\n",min(dp[1][1],dp[1][0]));71 return ;72 }73 int t;74 int main(){75 scanf("%d",&t);76 while(t--){77 scanf("%d",&n);78 init();79 for(int i=1;i<=n;i++){80 scanf("%d",&la[i][0]);81 }82 for(int i=1;i<=n;i++){83 scanf("%d",&la[i][1]);84 }85 int u,v,a,b,c,d;86 for(int i=1;i<=n-1;i++){87 scanf("%d%d%d%d%d%d",&u,&v,&a,&b,&c,&d);88 bel[v][0][0]=a;89 bel[v][0][1]=b;90 bel[v][1][0]=c;91 bel[v][1][1]=d;92 G[u].push_back(v);93 }94 Bfs();//分层95 solve();96 }97 return 0;98 }
HDU 2196
题意：给定一棵树，分别求1..N分别作为树根时，最长的树枝长是多少？
分析：两遍dfs,第一遍处理出（以1为根节点）:
int max1[maxn];//以1为根，i节点的最长路径int max2[maxn];//以1为根，i节点的次长路径，保证最长边的下一点不在这条路径上记录下相应的下一个节点的编号：
int max1id[maxn];int max2id[maxn];
第二遍处理出：转移节点后每个点作为根节点点的max1和max2，dfs搜索更新，这样从1号节点开始，每次转移，就能求出每个节点的情况了。
自己注意：向最长路径上的点转移时，长度是不会加一的。
具体看代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <vector> 5 #define maxn 10100 6 using namespace std; 7 8 vector<int>G[maxn]; 9 vector<int>len[maxn];10 int N;11 int max1[maxn];//以1为根，i节点的最长路径12 int max2[maxn];//以1为根，i节点的次长路径，保证最长边的下一点不在这条路径上13 int max1id[maxn];14 int max2id[maxn];15 void init(){16 for(int i=0;i<=N;i++){17 G[i].clear();18 len[i].clear();19 }20 }21 bool vis[maxn];22 void dfs1(int u,int fa){23 max1[u]=0;24 max2[u]=0;25 for(int i=0;i<G[u].size();i++){26 int v=G[u][i];27 if (v==fa) continue;28 dfs1(v,u);29 if (max1[v]+len[u][i]>max2[u]){//这个方法真机智啊30 max2[u]=max1[v]+len[u][i];31 max2id[u]=v;32 }33 if (max1[u]<max2[u]){34 swap(max1[u],max2[u]);35 swap(max1id[u],max2id[u]);36 }37 }38 return;39 }40 void dfs2(int u,int fa){41 for(int i=0;i<G[u].size();i++){42 int v=G[u][i];43 if (v==fa) continue;44 //用u去更新v45 if (max1id[u]==v){46 if (max2[v]<max2[u]+len[u][i]){47 max2[v]=max2[u]+len[u][i];48 max2id[v]=u;49 }50 }else {51 if (max2[v]<max1[u]+len[u][i]){52 max2[v]=max1[u]+len[u][i];53 max2id[v]=u;54 }55 }56 if (max2[v]>max1[v]){57 swap(max2[v],max1[v]);58 swap(max2id[v],max1id[v]);59 }60 dfs2(v,u);61 }62 return ;63 }64 int main()65 {66 while(~scanf("%d",&N)){67 init();68 int v,c;69 for(int i=2;i<=N;i++){70 scanf("%d%d",&v,&c);71 G[i].push_back(v);72 G[v].push_back(i);73 len[i].push_back(c);74 len[v].push_back(c);75 }76 dfs1(1,-1);77 dfs2(1,-1);78 for(int i=1;i<=N;i++) printf("%d\n",max1[i]);79 }80 81 return 0;82 }
POJ 4045
题意：这个题大致意思是给你一颗树，让你求一点，使该点到其余各点的距离之和最小。如果这样的点有多个，则按升序依次输出。
分析：cunt[x]记录以x为根的子树中节点的个数
dp[x]记录以x为根时，x到所有节点的距离之和
第一遍dfs处理这两个
又是一道根节点转移的题目
vsum=sum-cunt[v]-1+(N-cunt[v]-2)+1;
sum是以当前节点u为根时的所求值，vsum是将根转移到v节点上，所以v节点形成的子树整体上移，深度都减少了1，而其他节点深度都增加了1，这个在纸上画一画就明白了。
所以dfs就能搞定了
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <vector> 5 #include <algorithm> 6 #include <map> 7 #include <string> 8 #include <queue> 9 #define LL long long10 #define maxn 5100011 using namespace std;12 vector<int>G[maxn];13 LL dp[maxn];14 LL cunt[maxn];15 bool vis[maxn];16 LL Min;17 int cnt=0;18 int ans[maxn];19 void init(){20 for(int i=0;i<maxn;i++) G[i].clear();21 memset(dp,0,sizeof(dp));22 memset(cunt,0,sizeof(cunt));23 }24 LL dfs1(int u){25 LL ans=0;26 for(int i=0;i<G[u].size();i++){27 int v=G[u][i];28 if (vis[v]) continue;29 vis[v]=true;30 ans+=dfs1(v)+1;31 }32 return cunt[u]=ans;33 }34 LL dfs2(int u){35 LL ans=0;36 for(int i=0;i<G[u].size();i++){37 int v=G[u][i];38 if (vis[v]) continue;39 vis[v]=true;40 ans+=dfs2(v)+1+cunt[v];41 }42 return dp[u]=ans;43 }44 LL sum1,cunt1;45 LL N,I,R;46 void dfs3(int u,LL sum){47 LL vsum=0;48 for(int i=0;i<G[u].size();i++){49 int v=G[u][i];50 if (vis[v]) continue;51 vsum=sum-cunt[v]-1+(N-cunt[v]-2)+1;52 if (vsum==Min) ans[cnt++]=v;53 if (vsum<Min) {54 cnt=0;55 ans[cnt++]=v;56 Min=vsum;57 }58 LL cu=cunt[u],cv=cunt[v];59 cunt[v]=N-1;60 cunt[u]=N-cv-2;61 vis[v]=true;62 dfs3(v,vsum);63 cunt[v]=cv,cunt[u]=cu;64 }65 return ;66 }67 int t;68 int main(){69 scanf("%d",&t);70 while(t--){71 init();72 scanf("%lld%lld%lld",&N,&I,&R);73 for(int i=1;i<=N-1;i++){74 int u,v;75 scanf("%d%d",&u,&v);76 G[u].push_back(v);77 G[v].push_back(u);78 }79 memset(vis,0,sizeof(vis));vis[1]=true;80 cunt1=dfs1(1);81 memset(vis,0,sizeof(vis));vis[1]=true;82 sum1=dfs2(1);83 Min=sum1;cnt=0;84 ans[cnt++]=1;85 memset(vis,0,sizeof(vis));vis[1]=true;86 dfs3(1,sum1);87 sort(ans,ans+cnt);88 printf("%lld\n",Min*I*I*R);89 for(int i=0;i<cnt;i++){90 if (i==cnt-1) printf("%d\n",ans[i]);91 else printf("%d ",ans[i]);92 }93 printf("\n");94 }95 return 0;96 }
POJ 3342
题意：和第二题很想，父亲和孩子不能都选择，但是要判断选择的方案是否唯一
分析：讨论一下新增部分，
新增dup[x][0]、dup[x][1]分别表示选与不选是否唯一
memset(dup,0,sizeof(dup));//1表示确定，0不确定
其中v就是son节点if ((dp[v][0]>dp[v][1]&&dup[v][0]==0)||(dup[v][1]>dup[v][0]&&dup[v][1]==0)||(dp[v][1]==dp[v][0])) dup[u][0]=0;if (dup[v][0]==0) dup[u][1]=0;
我们判断dp[v][0]和dp[v][1]哪个大，这样dup[v][0]的状态就延续上去了（当然是必然选择的那个状态延续），当然若dp[v][1]==dp[v][0]，dup就是0了
dup需要赋初值1已做标记1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <vector> 5 #include <map> 6 #include <string> 7 #include <queue> 8 #define maxn 310 9 using namespace std; 10 //map存储标号 11 //边读边记录边的关系 12 //bfs分层记录每层节点 13 //从底层向上层dp 14 vector<int> G[maxn]; 15 vector<int> Ceil[maxn]; 16 map<string,int>Mp; 17 int n,cnum,cnt;//人数，分层数 18 void init(){ 19 for(int i=0;i<maxn;i++) G[i].clear(); 20 for(int i=0;i<maxn;i++) Ceil[i].clear(); 21 cnum=0;cnt=0; 22 Mp.clear(); 23 return ; 24 } 25 typedef pair<int,int>PAIR; 26 bool vis[maxn]; 27 void Bfs(){ 28 queue<PAIR> Q ; 29 Q.push(make_pair(1,1)); 30 memset(vis,0,sizeof(vis)); 31 vis[1]=true; 32 while(!Q.empty()){ 33 PAIR New=Q.front(); 34 Q.pop(); 35 int u=New.first; 36 int st=New.second; 37 Ceil[st].push_back(u); 38 cnum=max(cnum,st); 39 for(int i=0;i<G[u].size();i++){ 40 int v=G[u][i]; 41 if (vis[v]) continue; 42 Q.push(make_pair(v,st+1)); 43 vis[v]=true; 44 } 45 } 46 return; 47 } 48 int dp[maxn][2];//0表示不选择i节点，1表示选择i节点 49 int dup[maxn][2]; 50 void solve(){ 51 memset(dup,0,sizeof(dup));//1表示确定，0不确定 52 memset(dp,0,sizeof(dp)); 53 for(int i=0;i<Ceil[cnum].size();i++){ 54 int u=Ceil[cnum][i]; 55 dp[u][0]=0;dp[u][1]=1; 56 dup[u][0]=dup[u][1]=1; 57 } 58 for(int i=cnum-1;i>=1;i--){ 59 for(int j=0;j<Ceil[i].size();j++){ 60 int u=Ceil[i][j]; 61 dup[u][0]=dup[u][1]=1; 62 for(int k=0;k<G[u].size();k++){ 63 int v=G[u][k]; 64 dp[u][0]+=max(dp[v][0],dp[v][1]); 65 dp[u][1]+=dp[v][0]; 66 if ((dp[v][0]>dp[v][1]&&dup[v][0]==0)||(dup[v][1]>dup[v][0]&&dup[v][1]==0)||(dp[v][1]==dp[v][0])) 67 dup[u][0]=0; 68 if (dup[v][0]==0) dup[u][1]=0; 69 } 70 dp[u][1]++; 71 } 72 } 73 if (dp[1][0]==dp[1][1]){ 74 printf("%d No\n",dp[1][0]); 75 } 76 if (dp[1][0]>dp[1][1]){ 77 printf("%d ",dp[1][0]); 78 if (dup[1][0]) puts("Yes");else puts("No"); 79 } 80 if (dp[1][1]>dp[1][0]){ 81 printf("%d ",dp[1][1]); 82 if (dup[1][1]) puts("Yes");else puts("No"); 83 } 84 return; 85 } 86 int main(){ 87 string s; 88 char s1[55],s2[55]; 89 while(~scanf("%d",&n)&&n){ 90 init(); 91 scanf("%s",s1); 92 Mp[s=s1]=++cnt; 93 for(int i=1;i<n;i++){ 94 scanf("%s",s1);scanf("%s",s2); 95 int u,v; 96 if (Mp.count(s=s1)) u=Mp[s=s1]; 97 else u=Mp[s=s1]=++cnt; 98 if (Mp.count(s=s2)) v=Mp[s=s2]; 99 else v=Mp[s=s2]=++cnt;100 G[v].push_back(u);101 }102 Bfs();//分层103 solve();104 }105 return 0;106 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。