首页 > 代码库 > SGU149 Computer Network
SGU149 Computer Network
题解:
与树的路径有关的题目,挺赞的一道题目
首先树的一个节点,他的最远点,要么在他的子树,要么在他的父节点的子树中
那么我们先求出每个节点的子树中的最远点和次远点。然后求父节点的中的最远点。
在父节点中,如果该点不在父节点的最远路径上,那么该父节点的最远点则是最优的,否则次远点是最优的
但是不知道如何实现啊。。。。。。看了别人的代码
代码:
#include<iostream>#include<cstdio>#include<vector>#include<cstring>#include<cmath>#include<queue>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 2097152typedef pair<int,int> P;const double eps=1e-9;const int maxn=10100;const int mod=1e9+7;int First_son[maxn],Second_son[maxn],First_fa[maxn];int First_son_point[maxn];struct Edge{ int to,nxt,w;}edge[maxn*2];int head[maxn],p[maxn];int cnt,n,u,w;void addEdge(int u,int v,int w){ edge[cnt].to=v; edge[cnt].w=w; edge[cnt].nxt=head[u]; head[u]=cnt++;}//将无根树化为有根树,根为1 void dfs(int u,int fa){ p[u]=fa; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v!=fa) dfs(v,u); }}//找子树中的最远节点和次远节点,因为是子树,是从下到上更新,先dfs1 void dfs1(int u){ First_son[u]=Second_son[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v==p[u]) continue; dfs1(v); if(Second_son[u]<First_son[v]+edge[i].w){ Second_son[u]=First_son[v]+edge[i].w; if(First_son[u]<Second_son[u]){ First_son_point[u]=v; swap(First_son[u],Second_son[u]); } } }}//找寻父节点中的最远节点,是从上到下,所以是后dfs2 void dfs2(int u){ for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v==p[u]) continue; if(v==First_son_point[u]) First_fa[v]=edge[i].w+max(Second_son[u],First_fa[u]); else First_fa[v]=edge[i].w+max(First_son[u],First_fa[u]); dfs2(v); }}int main(){ cnt=0; memset(head,-1,sizeof(head)); scanf("%d",&n); for(int v=2;v<=n;v++){ scanf("%d%d",&u,&w); addEdge(u,v,w); addEdge(v,u,w); } dfs(1,-1); dfs1(1); dfs2(1); for(int i=1;i<=n;i++) printf("%d\n",max(First_son[i],First_fa[i])); return 0;}
SGU149 Computer Network
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。