首页 > 代码库 > ADO.NET,EF,Nhibernate比较
ADO.NET,EF,Nhibernate比较
题目传送门
题意:
给出一棵树,求离每个节点最远的点的距离
思路:
把无根树转化成有根树分析,
对于上面那棵树,要求距结点2的最长距离,那么,就需要知道以2为顶点的子树(蓝色圈起的部分,我们叫它Tree(2)),距顶点2的最远距离L1
还有知道2的父节点1为根节点的树Tree(1)-Tree(2)部分(即红色圈起部分),距离结点1的最长距离+dist(1,2) = L2,那么最终距离结点2最远的距离就是max{L1,L2}
f[i][0],表示顶点为i的子树的,距顶点i的最长距离
f[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离
要求所有的f[i][0]很简单,只要先做一次dfs求每个结点到叶子结点的最长距离即可。
然后要求f[i][1], 可以从父节点递推到子节点,
假设节点u有n个子节点,分别是v1,v2...vn
那么
如果vi不是u最长距离经过的节点,f[vi][1] = dist(vi,u)+max(f[u][0], f[u][1])
如果vi是u最长距离经过的节点,那么不能选择f[u][0],因为这保存的就是最长距离,要选择Tree(u)第二大距离secondDist,
可得f[vi][1] = dist(vi, u) + max(secondDist, f[u][1])
贴一段自己AC的代码:
<pre name="code" class="cpp">//求树的最长路径问题 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 10100 struct node { int id; int next; int len; }; struct node edge[MAXN*2]; int head[MAXN]; //用来表示头节点 int d[MAXN][2]; //用来表示状态集 int smaxn[MAXN];//次大距离 int smaxnid[MAXN]; //次最大值所经过的子节点 int maxnid[MAXN]; //最大值所经过的子节点 int ptr; void init() { ptr=0; memset(head,-1,sizeof(head)); } void addEdge(int a,int b,int len) //树形DP模版和上一篇一样的 { edge[ptr].id=b; edge[ptr].next=head[a]; edge[ptr].len=len; head[a]=ptr++; edge[ptr].id=a; edge[ptr].next=head[b]; edge[ptr].len=len; head[b]=ptr++; } //求所有节点的d[v][0],同时记录最大距离和第二大距离从哪个子节点过来,p是U的父节点,该函数用来求u节点到叶子节点 void fds1(int u,int p) { d[u][0]=0; smaxn[u]=0; int i; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].id; if(v==p) continue; fds1(v,u); if(smaxn[u]<d[v][0]+edge[i].len) { smaxn[u]=d[v][0]+edge[i].len; smaxnid[u]=v; if(smaxn[u]>d[u][0]) { swap(smaxn[u],d[u][0]); swap(smaxnid[u],maxnid[u]); } } } } //求所有节点的d[v][1],u为v的父节点,p为u的父节点 void fds2(int u,int p) { int i; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].id; if(v==p) continue ; if(v!=maxnid[u]) d[v][1]=edge[i].len+max(d[u][0],d[u][1]); else d[v][1]=edge[i].len+max(smaxn[u],d[u][1]); fds2(v,u); } } int main() { //freopen("a.txt","r",stdin); int n,i,v,len; while(scanf("%d",&n)!=EOF) { init(); for(i=2;i<=n;i++) { scanf("%d%d",&v,&len); addEdge(i,v,len); } fds1(1,-1); fds2(1,-1); for(i=1;i<=n;i++) printf("%d\n",max(d[i][0],d[i][1])); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。