首页 > 其他分享 >洛谷P8602 大臣的旅费

洛谷P8602 大臣的旅费

时间:2023-11-19 17:56:47浏览次数:35  
标签:洛谷 int ll d% dfs 旅费 P8602 include maxd

这道题既可以用图论多次求单源最短路暴力来做,也可以用正解:求树的直径来做。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5, M = N << 1;

int n, cnt, h[N], e[M], w[M], ne[M];

inline void add(int a, int b, int c)
{
    e[++cnt] = b;
    w[cnt] = c;
    ne[cnt] = h[a];
    h[a] = cnt;
}
int t, maxd, maxu;

void dfs(int u, int fa,int dis)
{
    if(dis > maxd)
    {
        maxd = dis;
        maxu = u;
    }
    for(int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u, dis + w[i]);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    dfs(1, 0, 0);
    dfs(maxu, 0, 0);
    ll ans = (ll) maxd * 10L +(ll) maxd * (maxd + 1) / 2;
    printf("%lld\n", ans);
    system("pause");
    return 0;
}

 

标签:洛谷,int,ll,d%,dfs,旅费,P8602,include,maxd
From: https://www.cnblogs.com/smartljy/p/17842335.html

相关文章

  • 【洛谷 P1125】[NOIP2008 提高组] 笨小猴 题解(字符串+映射+集合)
    [NOIP2008提高组]笨小猴题目描述笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:假设是单词中出现次数最多的字母的出现次数,是单词中出现次数最少的字母的出现次数,......
  • 洛谷B2017 打印 ASCII 码(Python3)
    要点:1.Python的input()默认要换行,而在输入的时候即使只输了一个字符,也会被判定为输入两个字符。故此处要么只取字符串的第一位,要么在输入时用.strip()来删去首位字符,strip的介绍在这里2.Python中不能用强制类型转换来得到ASCII码,需要用到ord()函数。ord():括号内的字符的ASCI......
  • 洛谷B2016 浮点数向零舍入(Python3)
    要点:1.有正有负怎么办?正负分开写?如果只看数字部分,那取整的方式是一样的。所以我们可以先输出符号,把问题全都转化到非负数集中。2.如何取整?此处取整为向下取整。而强制类型转换把浮点数转化为整型数的时候是把小数部分全部去掉,而不是四舍五入,与题中取整方式相符,故可直......
  • 洛谷 P9869 [NOIP 2023] 三值逻辑 题解
    https://www.luogu.com.cn/problem/P9869?contestId=145259看到要给变量赋初始值,还是T,F,U之类的,容易想到2-SAT。设\(1\simn+m\)的点表示\(x_1,x_2,\dots,x_{n+m}\)为T的点,其中\(x_{k+n}(1\leqk\leqm)\)表示在第\(k\)次操作被操作的变量的值(操作......
  • 洛谷 B2006 地球人口承载力估计(Python3)
    这题难点在理解题意。没有任何技术含量:(题目分析:1.“可持续发展”到底什么意思?Makeendsmeet.也就是说能养活的那些人一年消耗的等于地球一年产生的。2.题中为什么要给x,a,y,b?为了求等量关系。注意,这里"x 亿人生活 a 年,或供 y 亿人生活 b年"用的是地球新生的资源和原有......
  • 【洛谷 P2141】[NOIP2014 普及组] 珠心算测验 题解(集合+多重循环)
    [NOIP2014普及组]珠心算测验题目描述珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合......
  • 洛谷p1090__合并果子
    合并果子可以作为mulitset的板子题 mulitset的accode#include<iostream>#include<set>usingnamespacestd;multiset<int,less<int>>m;intmain(){intn;cin>>n;for(inti=0;i<n;i++){intt;cin>......
  • 【LGR-166-Div.4】洛谷入门赛17
    【LGR-166-Div.4】洛谷入门赛#17比赛地址这次是div4的难度,整体不算是很难,很适合小白玩家[10月入门赛-A]食堂题目描述为了给师生提供良好的用餐体验,洛谷小学的食堂坚持现炒、现做每一道菜肴。洛谷小学一共有\(a\)名老师和\(b\)名学生。食堂的营养师为每位师生的用餐进......
  • 【洛谷 P1089】[NOIP2004 提高组] 津津的储蓄计划 题解(循环)
    [NOIP2004提高组]津津的储蓄计划题目描述津津的零花钱一直都是自己管理。每个月的月初妈妈给津津元钱,津津会预算这个月的花销,并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末她会加上还给津津。因此津津制定了一......
  • 洛谷 P1931 题解
    三倍经验P1931UVA436SP9340题意给你\(n(n\le30)\)种货币及\(m\)种汇率,问是否出现套利的情况。怎么没给\(m\)的范围啊思路首先把汇率抽象成一张图。容易发现,若一个单位的某种货币经过一个环获得了大于一的代价,说明出现了套利。具体来说,考虑Floyd,若$\existsi\in......