2 条题解

  • 1
    @ 2022-12-9 16:25:21
    #include <bits/stdc++.h>
    using namespace std;
    int n;
    struct Edge
    {
        int v, w;
    };
    vector<Edge> e[1005];
    int dis[1005];
    // 当前子树根节点,当前子树根节点的父节点
    void dfs(int u, int fa)
    {
        // 枚举所有u能连到的点v
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (v == fa)
                continue; // 忽略父节点方向
            dis[v] = dis[u] + w;
            dfs(v, u);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            e[u].push_back((Edge){v, w});
            e[v].push_back((Edge){u, w});
        }
        int root, maxDisNode;
        //以1号点作为根节点找一下最远的
    	root = 1; 
        dis[root] = 0;
        dfs(root, 0);
        maxDisNode = 1;
        for(int i = 1; i <= n; i++)
        	if(dis[i] > dis[maxDisNode])
        		maxDisNode = i;
        //以maxDisNode作为根节点找一下最远的
    	root = maxDisNode;   
        dis[root] = 0;
        dfs(root, 0);
        maxDisNode = 1;
        for(int i = 1; i <= n; i++)
        	if(dis[i] > dis[maxDisNode])
        		maxDisNode = i;
        //输出答案 
        cout << dis[maxDisNode] << " ";
        return 0;
    }
    
    

    #include <bits/stdc++.h>
    using namespace std;
    int n;
    struct Edge
    {
        int v, w;
    };
    vector<Edge> e[1005];
    int dis[1005];
    int maxDisNode = 1;
    // 当前子树根节点,当前子树根节点的父节点
    void dfs(int u, int fa)
    {
        if (dis[u] > dis[maxDisNode])
            maxDisNode = u;
        // 枚举所有u能连到的点v
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].v;
            int w = e[u][i].w;
            if (v == fa)
                continue; // 忽略父节点方向
            dis[v] = dis[u] + w;
            dfs(v, u);
        }
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n - 1; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            e[u].push_back((Edge){v, w});
            e[v].push_back((Edge){u, w});
        }
        dis[1] = 0;
        dfs(1, 0);
        dis[maxDisNode] = 0;
        dfs(maxDisNode, 0);
        cout << dis[maxDisNode] << " ";
        return 0;
    }
    
    • 0
      @ 2022-12-10 17:50:50
      #include<bits/stdc++.h>
      using namespace std;
      struct twig{
      	int to;
      	int len;
      };
      int n,x,y,z;
      vector<twig> a[1005];
      int depth[1005];
      void dfs(int now,int fa)
      {
      	if(!a[now].empty())
      		for(auto it=a[now].begin();it!=a[now].end();it++)
      		{
      			int w=(*it).to,length=(*it).len;
      			if(w!=fa)
      			{
      				depth[w]=depth[now]+length;
      				dfs(w,now);
      			}
      		}
      }
      int main()
      {
      	cin>>n;
      	for(int i=1;i<n;i++)
      	{
      		cin>>x>>y>>z;
      		a[x].push_back((twig){y,z});
      		a[y].push_back((twig){x,z});
      	}
      	int maxdisroot=1,maxdis=0;
      	//寻找到点 1  距离最远的点 maxdisroot 
      	dfs(1,-1);
      	for(int i=1;i<=n;i++)
      		if(maxdis<depth[i])
      		{
      			maxdis=max(maxdis,depth[i]);
      			maxdisroot=i;
      		}
      	//以maxdisroot为根节点 寻找最长路径 
      	memset(depth,0,sizeof(depth));//清空 
      	dfs(maxdisroot,-1);
      	for(int i=1;i<=n;i++)
      		maxdis=max(maxdis,depth[i]);
      	cout<<maxdis;
      	return 0;
      }
      
      • 1

      信息

      ID
      1195
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      递交数
      53
      已通过
      30
      上传者