P1268-树的重量

墨蓝 2023-06-01 08:47 11阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define pb push_back
     4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
     5 #define INF 100000003
     6 #define ll long long
     7 inline ll read()
     8 {
     9     ll ans = 0;
    10     char ch = getchar(), last = ' ';
    11     while(!isdigit(ch)) last = ch, ch = getchar();
    12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    13     if(last == '-') ans = -ans;
    14     return ans;
    15 }
    16 inline void write(ll x)
    17 {
    18     if(x < 0) x = -x, putchar('-');
    19     if(x >= 10) write(x / 10);
    20     putchar(x % 10 + '0');
    21 }
    22 int n;
    23 int a[40][40];
    24 int main()
    25 {
    26     while(~scanf("%d",&n))
    27     {
    28         if(!n)
    29             break;
    30         _for(i,1,n+1)
    31             _for(j,1,n+1)
    32                 if(i<j)
    33                     a[i][j] = a[j][i] = read();
    34         
    35         
    36         int ans = 0;
    37         _for(i,3,n+1)
    38         {
    39             int t = INT_MAX;
    40             _for(j,2,i)
    41             {
    42                 t = min(t,(a[1][i]+a[i][j]-a[1][j])/2);
    43             }
    44             ans += t;
    45         }
    46         printf("%d\n",ans+a[1][2]);
    47     }
    48     
    49     return 0;
    50 }

转载于:https://www.cnblogs.com/Asurudo/p/11527606.html

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 P35 JTree树

P35 JTree树 1.概述 2.节点（DefaultMutableTreeNode） 3.路径（TreePath） 4.树（JTree）

深碍√TFBOYSˉ_/ 2024年04月06日 09:51/ 0 赞/ 59 阅读

相关【线段树】P6492 STEP

[P6492 \[COCI2010-2011\6\] STEP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P6492 _COCI2010-2011_6

深碍√TFBOYSˉ_/ 2024年03月17日 15:04/ 0 赞/ 89 阅读

相关 LeetCode_前缀树_中等_1268.搜索推荐系统

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个产品数组 products 和一个字符串 searchWord ，prod

￡神魔★判官ぃ/ 2023年10月13日 17:47/ 0 赞/ 34 阅读

相关题解 Luogu P1099 【树网的核】

这题是真的水啊。。。 \------------ 昨天模拟赛考了这题,很多人都是O($n^3$)水过，但我认为，要做就做的足够好(其实是我根本没想到O($n^3$)的做法)

青旅半醒/ 2023年06月01日 12:42/ 0 赞/ 14 阅读

相关 P1484-种树

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

约定不等于承诺〃/ 2023年06月01日 08:55/ 0 赞/ 14 阅读

相关 P1087-FBI树

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

迈不过友情╰/ 2023年06月01日 08:50/ 0 赞/ 11 阅读

相关 P1268-树的重量

1 include <bits/stdc++.h> 2 using namespace std; 3 define pb push_back

墨蓝/ 2023年06月01日 08:47/ 0 赞/ 12 阅读

相关知识点：二叉（重量）平衡树——替罪羊树

目录知识点概要知识点详解平衡因子子树的重构基础操作复杂度分析关于替罪

亦凉/ 2021年12月14日 10:45/ 0 赞/ 302 阅读

相关 P2590 [ZJOI2008]树的统计

题目描述一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的

迷南。/ 2021年11月26日 07:36/ 0 赞/ 200 阅读

相关 P5018对称二叉树

[传送][Link 1] ![1605842-20190701182450144-342871989.png][] ![1605842-20190701182511352-

柔情只为你懂/ 2021年11月11日 01:44/ 0 赞/ 291 阅读