关键词：
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737
求出树的重心，跑spfa
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
const int N = 1e5 + 10;
#define oo 999999999999
#define yxy getchar()
int n, now, Point, Min_siz;
int head[N] ,siz[N], Que[N << 1];
struct Node {int v, w, nxt;} G[N << 1];
bool vis[N];
long long dis[N];
inline int read(){
int x = 0; char c = yxy;
while(c < ‘0‘ || c > ‘9‘) c = yxy;
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = yxy;
return x;
}
inline void add(int u, int v, int w){
G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;
}
void dfs(int u, int father){
siz[u] = 1;
int Max_son = -1;
for(int i = head[u]; ~ i; i = G[i].nxt){
int v = G[i].v;
if(v != father){
dfs(v, u);
siz[u] += siz[v];
Max_son = max(Max_son, siz[v]);
}
}
Max_son = max(Max_son, n - siz[u]);
if(Max_son < Min_siz){
Min_siz = Max_son;
Point = u;
}
}
void spfa(int S){
for(int i = 1; i <= n; i ++) dis[i] = oo;
dis[S] = 0;
int H = 1, T = 1;
Que[H] = S;
while(H <= T){
int topp = Que[H ++];
vis[topp] = 0;
for(int i = head[topp]; ~ i; i = G[i].nxt){
int v = G[i].v;
if(dis[v] > dis[topp] + G[i].w){
dis[v] = dis[topp] + G[i].w;
if(!vis[v]) vis[v] = 1, Que[++ T] = v;
}
}
}
}
int main()
{
n = read();
for(int i = 1; i <= n; i ++) head[i] = -1;
for(int i = 1; i < n; i ++) {
int u = read(), v = read(), w = read();
add(u, v, w); add(v, u, w);
}
Min_siz = 999999999;
dfs(1, 0);
spfa(Point);
long long Answer = 0;
for(int i = 1; i <= n; i ++) Answer += dis[i];
cout << Answer;
return 0;
}
51nod1737配对（树的重心）
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737题意： 思路：树的重心。树的重心就是其所以子树的最大的子树结点数最少，删除这个点后最大连通块的结点数最小，也就说各个连通块尽量平衡。这道题的话就是先求一个... 查看详情
51nod2006飞行员配对（二分图最大匹配）
链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=2006思路：二分匹配注意nm的关系代码：1#include<iostream>2#include<string.h>3usingnamespacestd;4intg[105][105],vis[105],who[105];5intn,m;6bo 查看详情
[51nod][cf468d]1558树中的配对
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1558 不是很懂dalao们用线段树是怎么写的……反正找出重心以后每个子树一个堆，再来个全局堆就吼了#include<queue>#include<stdio.h>#include<algorithm>#defineMN1000 查看详情
51nod2006飞行员配对(二分图最大匹配)
...员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一 查看详情
51nod2006飞行员配对(二分图最大匹配)-匈牙利算法
2006 飞行员配对(二分图最大匹配)题目来源： 网络流24题基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。... 查看详情
51nod2006飞行员配对(二分图最大匹配)匈牙利匹配
2006 飞行员配对(二分图最大匹配)题目来源： 网络流24题基准时间限制：1 秒空间限制：131072 KB分值: 0 难度：基础题 收藏 关注第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。... 查看详情
51nod2006飞行员配对(二分图最大匹配)裸匈牙利算法求二分图最大匹配题
题目： 题目已经说了是最大二分匹配题，查了一下最大二分匹配题有两种解法，匈牙利算法和网络流。看了一下觉得匈牙利算法更好理解，然后我照着小红书模板打了一遍就过了。 匈牙利算法：先试着把没用过... 查看详情
51nod2006飞行员匹配
2006飞行员配对(二分图最大匹配) 第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员，其中1名是英国飞行员，另1名... 查看详情
（二分图最大匹配）51nod2006飞行员配对(代码片段)
...员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的... 查看详情
51nod算法马拉松21(迎新年)
...比赛经过吧。8:00准时发题，拿到之后第一时间开始读。A配对，看上去像是二分图最大权匹配，一看范围吓傻了，先跳过读后面的题。B完全二叉树的方差，大概看了一遍，好神的样子，跳过。C多项式？好吧没学过FFT和NTT的我肯... 查看详情
51nod——t1631小鲨鱼在51nod小学
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1631基准时间限制：1 秒空间限制：131072 KB分值: 20 难度：3级算法题 收藏 关注鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面... 查看详情
51nod1185||51nod1072威佐夫博弈
贴个模板：平常的跟高精度java的；int：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<alg 查看详情
51nod1631小鲨鱼在51nod小学
...题鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面的特长，在班里担任了许多职务。 每一个职务都有一个起始时间A和结束时间B，意为小鲨鱼在[A,B]时间内，担任了某职务(inclusively)。 现在... 查看详情
51nod1354：选数字
51nod1354：选数字题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354题目大意：有$T(Tleqslant20)$组数据，每组给出$n(nleqslant1000)$个数和$K(Kleqslant100,000,000)$，问在这$n$个数中选取若干个，积为$K$的方案数有多少.DP+离散化与... 查看详情
51nod1310：chandrimaandxor
51nod1310：ChandrimaandXOR题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1310题目大意：序列$S={1,2,4,5,...}$，其中任何一个数转为二进制不包括两个连续的$1$。给出一个长度为$N$的正整数数组$A$，$A_1,A_2,...,A_n$记录的是下标... 查看详情
51nod1232：完美数
51nod1232：完美数题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1232题目大意：如果一个数能够被组成它的各个非$0$数字整除，则称它是完美数。例如：$10$,$11$,$12$,$101$都是完美数，但是$13$就不是完美数（因为$13$不能... 查看详情
51nod2576
题意51nod做法令(f_n,d)为(d)层，目前维宽度为(n)(f_n,d=sumlimits_i=1^nf_i,d-1(n?i+1)^k)构造矩阵转移，上三角对角线相等矩阵，快速算就完了题外话一遍过qwq 查看详情
51nod1728
题意51nod做法要是想不到树就删号重练吧令(F_k)为深度不超过(k)的森林个数的EGF不超过(k)的森林，就是若干棵不超过(k)的树，取掉树的根，就是不超过(k-1)的森林就有(F_k=e^xF_k-1) 查看详情