牛客练习赛40 C 小A与欧拉路（树的直径）

链接：https://ac.nowcoder.com/acm/contest/369/C

题目描述

小A给你了一棵树，对于这棵树上的每一条边，你都可以将它复制任意（可以为0）次（即在这条边连接的两个点之间再加一条边权相同的边），求所有可能新形成的图中欧拉路的最短长度

欧拉路：从图中任意一个点开始到图中任意一个点结束的路径，并且图中每条边只通过恰好一次

输入描述:

第一行一个数 n ，表示节点个数

接下来 n-1 行，每行三个整数 u,v,w，表示有一条 u 到 v 边权为 w 的无向边

保证数据是一棵树

输出描述:

一行一个整数，表示答案

输入

输出

5

题意：找一条最短路，可以遍历所有树的节点
题意：这是博主第二次写这种题了，只要找到树的直径，然后用 总权值*2-直径的权值 就是答案
本来以为可以直接a掉 结果脑残的用了刚刚学会的链式前向星，没有注意双向边数组两倍的细节 超时到自闭

#include <cstdio>

#include <map>

#include <iostream>

#include<cstring>

#include<bits/stdc++.h>

#define ll long long int

#define M 6

using namespace std;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int moth[]={,,,,,,,,,,,,};

int dir[][]={, ,, ,-, ,,-};

int dirs[][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};

const int inf=0x3f3f3f3f;

const ll mod=1e9+;

int n,cnt;

struct node{

    int next;

    int to;

    int w;

};

node edge[];

int head[];

bool vis[];

void add(int u,int v,int w){

    edge[++cnt].next=head[u];

    edge[cnt].to=v;

    edge[cnt].w=w;

    head[u]=cnt;

}

ll ans;

int ss;

void dfs(int pos,ll v){

    vis[pos]=;

    for(int i=head[pos];i!=;i=edge[i].next){

        if(vis[edge[i].to]) continue;

        dfs(edge[i].to,v+edge[i].w);

            vis[edge[i].to]=;

    }

    if(v>ans){

        ans=v;

        ss=pos;

    }

}

int main(){

    while(~scanf("%d",&n)){

        ll sum=;

        memset(head,,sizeof(head));

        memset(vis,,sizeof(vis));

        cnt=;

        for(int i=;i<n;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            sum+=w;

            add(u,v,w);

            add(v,u,w);

        }

        ans=;

        dfs(,);

        vis[]=;

        ans=;

        dfs(ss,);

        printf("%lld\n",sum*-ans);

    }

}

巴特西

牛客练习赛40 C 小A与欧拉路（树的直径）

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章