1.树的最长路径(直径)
#include<bits/stdc++.h> using namespace std; const int N=1e4+10,M=2*N; int h[N],e[M],ne[M],idx,w[M]; int ans; void add(int a,int b,int c)//领接表的方式存树 { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int dfs(int u,int f)//找以u为根的最大路径 { int d1=0,d2=0;//用来记录最大值和次大值 for(int i=h[u];~i;i=ne[i])//枚举一遍子树 { int j=e[i]; if(j==f) continue;//防止循环遍历 int d=dfs(j,u)+w[i];//该子树到u的最长距离 if(d>=d1) d2=d1,d1=d;//假如大于最大值,更新一遍最大值和次大值 else if(d>d2) d2=d;//假如大于次大值,则更新次大值 } ans=max(ans,d1+d2);//答案求一遍经过该点的最长路径 return d1;//返回u为根的最长距离,。记住这里是不经过u的距离 } int main() { int n; cin>>n; memset(h,-1,sizeof h); for(int i=1;i<n;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c);//无向图 } dfs(1,-1); cout<<ans<<endl; return 0; }
2 树的中心
#include<bits/stdc++.h> using namespace std; const int N=1e4+10,M=2*N,INF=0x3f3f3f3f; int h[N],e[M],ne[M],idx,w[M]; int up[N],d1[N],d2[N],p1[N],p2[N]; void add(int a,int b,int c)//领接表的方式存树 { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int dfs_d(int u,int f)//找以u为根的最大距离 { d1[u]=d2[u]=-INF;//把距离初始化为负无穷 for(int i=h[u];~i;i=ne[i])//枚举一遍子树 { int j=e[i]; if(j==f) continue;//防止循环遍历 int d=dfs_d(j,u)+w[i];//该子树到u的最长距离 if(d>=d1[u]) //假如大于最大值,更新一遍最大值和次大值 { d2[u]=d1[u],p2[u]=p1[u];//最大值经过的点也更新一下 d1[u]=d,p1[u]=j;//次大值经过的点也更新一下 } else if(d>d2[u]) d2[u]=d,p2[u]=j;//假如大于次大值,则更新次大值,次大值的点也更新一下 } if(d1[u]==-INF) d1[u]=d2[u]=0;//假如没更新过,则让其距离为0 return d1[u];//返回u为根的最长距离 } void dfs_u(int u,int f)//求一遍向上走的最大距离 { for(int i=h[u];~i;i=ne[i])//枚举子树 { int j=e[i]; if(j==f) continue;//防止循环遍历 if(p1[u]==j) up[j]=max(up[u],d2[u])+w[i];//假如该子树向上走的最大距离经过自己,则用次大值更新自己 else up[j]=max(up[u],d1[u])+w[i];//假如不经过自己,则用向上走的最大值更新自己 dfs_u(j,u); } } int main() { int n; cin>>n; memset(h,-1,sizeof h); for(int i=1;i<n;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c);//无向图 } dfs_d(1,-1);//向下走 dfs_u(1,-1);//向上走 int ans=INF; for(int i=1;i<=n;i++) ans=min(ans,max(up[i],d1[i]));//求一遍每个点的最小距离 cout<<ans<<endl; return 0; }
3 数字转换
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
由于一个数的约数和是确定的,所以以约数和为根,当前是也子节点来领接
#include<bits/stdc++.h> using namespace std; const int N=5e4+10; int h[N],e[N],idx,ne[N]; int sum[N]; bool st[N];//用来标记该点的有父节点 int ans; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int dfs(int u)//求以u为根的最长距离 { int d1=0,d2=0;//记录子树的最大值与次大值 for(int i=h[u];~i;i=ne[i])//枚举子节点 { int j=e[i]; int d=dfs(j)+1;//距离加1,多一步 if(d>=d1) d2=d1,d1=d;//假如大于最大值,则更新最大值与次大值 else if(d>d2) d2=d;//假如大于次大值,则 } ans=max(ans,d1+d2);//更新最大值 return d1;//返回u为根的最大距离 } int main() { int n; cin>>n; memset(h,-1,sizeof h); for(int i=1;i<=n;i++)//求一个数的约数和 for(int j=2;j<=n/i;j++)//用类似质数筛的方法 sum[i*j]+=i;//该数加上这个约数 for(int i=2;i<=n;i++)//因为1没有在约了,所以从0开始 if(sum[i]<i)//假如满足条件 { add(sum[i],i);//把i的父节点令为sum【i】 st[i]=true;//标记这个点有父节点 } for(int i=1;i<=n;i++) if(!st[i])//从根节点开始遍历 dfs(i); cout<<ans<<endl; return 0; }
4 二叉苹果树
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=110,M=2*N; int n,m; int h[N],e[M],idx,ne[M],w[M]; int f[N][M]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int father) { for(int i=h[u];~i;i=ne[i])//枚举物品组 { if(e[i]==father) continue; dfs(e[i],u); for(int j=m;j>=0;j--)//体积 for(int k=0;k<j;k++)//枚举决策 f[u][j]=max(f[u][j],f[u][j-k-1]+f[e[i]][k]+w[i]); } } int main() { cin>>n>>m; memset(h,-1,sizeof h); for(int i=1;i<n;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } dfs(1,-1); cout<<f[1][m]<<endl;//输出第一个根的m个树枝 return 0; }
5 战略游戏
#include<bits/stdc++.h> using namespace std; const int N=1510,M=2*N; int n; int h[N],e[M],idx,ne[M]; bool st[N]; int f[N][M]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u) { f[u][0]=0;//表示不放哨兵 f[u][1]=1;//表示放一个哨兵 for(int i=h[u];~i;i=ne[i])//枚举子树 { int j=e[i]; dfs(j); f[u][0]+=f[j][1];//当前没哨兵加上子树一定得有哨兵 f[u][1]+=min(f[j][0],f[j][1]);//当前有哨兵,子树可有可无 } } int main() { while(scanf("%d",&n)!=EOF) { memset(h,-1,sizeof h);//清空上一次的状态 idx=0;//清空上一次的状态 memset(st,0,sizeof st);//清空上一次的状态 for(int i=0;i<n;i++) { int a,cnt; scanf("%d:(%d)",&a,&cnt); while(cnt--) { int b; scanf("%d",&b); add(a,b); st[b]=true; } } int root=0; while(st[root]) root++;//找根节点 dfs(root); printf("%d\n",min(f[root][0],f[root][1]));//输出放或者不放的最小值 } return 0; }
6 皇宫看守
信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=1510,M=2*N; int n; int h[N],e[M],idx,ne[M],w[M]; bool st[N]; int f[N][M]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u) { f[u][2]=w[u];//表示放一个哨兵,所花费的费用 for(int i=h[u];~i;i=ne[i])//枚举子树 { int j=e[i]; dfs(j); f[u][0]+=min(f[j][1],f[j][2]);//当前被父节点看到,则子节点只能自己放或者被子节点的子节点看到,两边取最小 f[u][2]+=min(f[j][0],min(f[j][1],f[j][2]));//当前有哨兵,则子树三种情况都有可能,取最小 } f[u][1]=0x3f3f3f3f;//因为要求最小值,所以初始化为正无穷 for(int i=h[u];~i;i=ne[i])//枚举子树 { int k=e[i]; //这里f[u][0]就是以u根的子树所有f[j][1]与f[j][2]的最小值的和,因为前面更新状态时已经求过 //所以下面就得减去除第k的f[k][1],f[k][2]的最小值的和,剩下就是状态计算的所求 f[u][1]=min(f[u][1],f[k][2]+f[u][0]-min(f[k][1],f[k][2]));//表示第k个子树有哨兵,可以看到父节点,其他的只能是要么被儿子看到要么自己也放 } } int main() { cin>>n; memset(h,-1,sizeof h);//清空上一次的状态 for(int i=1;i<=n;i++) { int a,c,cnt; cin>>a>>c>>cnt; w[a]=c; while(cnt--) { int b; cin>>b; add(a,b); st[b]=true; } } int root=1; while(st[root]) root++;//找根节点 dfs(root); printf("%d\n",min(f[root][1],f[root][2]));//输出被子节点看到或者放的最小值 return 0; }