Gym 100796C Minimax Tree

2019-11-08 02:10:12

字体：大中小

来源：转载

供稿：网友

Gym 100796C Minimax Tree

dfs 编程能力想法

传送门：HustOJ

传送门：CodeForce

题意

给出一棵n个节点的树，有l个叶节点，每个叶节点都有一个value值。现有k个min标签，n-l-k个max标签，安排中间节点的标签，输出根节点可能的最大值和最小值。min标签表示向上传递儿子中的最小值，max传递最大值。

思路

主要是dfs。 %%%1 %%%2

就最小值来讲，要想让某一个节点的值最终传递到根节点，它的祖先节点中必须全部采用min标签，最大值亦然。

然后这题想想就会发现就是dfs，每递归一层，层数lev就要加一，求出每个节点可能的最大值与最小值。回溯时根据当前层数和标签数的关系写入当前节点的minmax值。

但是这样会挂在test11。

然后需要注意到，如果一个节点只有一个孩子，那么他向上传递的值与标签无关。所以dfs时，如果一个节点只有一个孩子，那么递归进他的孩子时lev数不加1就行了。

这是一个样例，单步一下看看回溯时minval[5]的值就明白了。

8 2 1 2 3 4 5 5 1 0 0 0 0 0 1 10 5

代码

#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <vector>#include <cmath>#include <queue>#include <stack>#define _ ios_base::sync_with_stdio(0);cin.tie(0);#define M(a,b) memset(a,b,sizeof(a));using namespace std;const int MAXN=100005;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;typedef long double LB;vector<int> son[MAXN];int valmin[MAXN], valmax[MAXN];int fa[MAXN];int dfsmin(int n, int lev, int mlev){ int res=oo, maval=0; if(son[n].size()==0) return valmin[n]; for(int i=0;i<son[n].size();i++) { int temp=dfsmin(son[n][i], son[n].size()==1 ? lev : lev+1, mlev); maval=max(maval, temp); res=min(res, temp); } return valmin[n]=(lev>mlev ? maval : res);}int dfsmax(int n, int lev, int mlev){ int res=0, mival=oo; if(son[n].size()==0) return valmax[n]; for(int i=0;i<son[n].size();i++) { int temp=dfsmax(son[n][i], son[n].size()==1 ? lev : lev+1, mlev); mival=min(mival, temp); res=max(res, temp); } return valmax[n]=(lev>mlev ? mival : res);}int main(){ _ int n; while(cin>>n) { int k;cin>>k; for(int i=0;i<=n;i++) son[i].clear(); M(valmin, 0);M(fa, -1); int leaf=0; for(int i=2;i<=n;i++) { int tt;cin>>tt; fa[i]=tt;son[tt].push_back(i); } for(int i=1;i<=n;i++) { int tt;cin>>tt; valmin[i]=tt; valmax[i]=tt; if(tt!=0) leaf++; } cout<<dfsmin(1, 1, k)<<' '; cout<<dfsmax(1, 1, n-k-leaf)<<endl; } return 0;}

上一篇：Scala学习笔记 --- 理解术语面向对象编程和函数式编程

下一篇：C#并发编程（一）