ural 1056 Computer Net(树形DP)需要用到两遍dfs-白红宇

ural 1056 Computer Net(树形DP)需要用到两遍dfs

阅读量：4036 次

发布时间：2019-05-24

本文共 1148 字，大约阅读时间需要 3 分钟。

1、

2、题目大意;

有n台计算机相连，已知1是根节点，现在要求的是谁是这个网络中的中心？

就是求每个点到其他点的最远距离中的最小距离的点

我们首先得求出每个点到其他点的最大距离来，然后找出这里边最小的距离对应的点是哪个

我们可以用两遍dfs求出来，

第一遍dfs，更新出每个结点的最远距离

第二次dfs,更新子节点是否可以通过自己的父节点可以到达更远的点

用dp[i][1]表示i点的最大值，dp[i][0]表示i点的次大值

最后只需要将dp[i][1]中最小的那个i值输出即可，可能不止一个

3、AC代码：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define N 10005#define INF 0x7fffffffvector
       
         adj[N*2];int visit[N];int dp[N][2],ans;//dp[i][1]记录i点的最大值，dp[i][0]记录i点的次大值void dfs1(int u){    visit[u]=1;    for(int i=0; i
        
         dp[u][1]) { dp[u][0]=dp[u][1]; dp[u][1]=dp[v][1]+1; } else if(dp[v][1]+1>dp[u][0]) { dp[u][0]=dp[v][1]+1; } } }}void dfs2(int u){ visit[u]=1; for(int i=0; i
         
          dp[v][1]) { dp[v][0]=dp[v][1]; dp[v][1]=tmp; } else if(tmp>dp[v][0]) { dp[v][0]=tmp; } if(ans>dp[v][1]) ans=dp[v][1]; dfs2(v); } }}int main(){ int n,a; scanf("%d",&n); for(int i=2; i<=n; i++) { scanf("%d",&a); adj[i].push_back(a); adj[a].push_back(i); } ans=INF; memset(visit,0,sizeof(visit)); dfs1(1); memset(visit,0,sizeof(visit)); dfs2(1); for(int i=1;i<=n;i++) { if(dp[i][1]==ans) printf("%d ",i); } printf("\n"); return 0;}