公司网站建设方案书,网站建设从入门到精通 网盘,深圳网站的优化,免费模板最多的视频制作软件》》》算法竞赛 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记#xff1a;转载… 》》》算法竞赛 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记转载需获得博主本人同意且需标明转载源* language C* Version 1.0还在学习中 */UpData Log 2023.9.26 更新进行中 Statement0 一起进步 Statement1 有些描述是个人理解可能不够标准但能达其意 技术提升站点 文章目录 》》》算法竞赛技术提升站点21 树上问题21-0 关于 树 的问题 有哪些21-1 树的重心21-1-1 重心是什么21-1-2 重心的性质21-1-2 重心的查找 教父poj 3107 21 树上问题
树 是 图 的一种特例 树 就是 “没有环” 的 连通图
判断一个 图 是否是一个 树需要满足的条件 1树根一棵树可以基于无向图与有向图区别在于树根。 基于无向图的树无根树是没有固定树根的也就是说树根的个数可能不止为1或说每个结点都能做为树根 基于有向图的树有根树有且仅有一个树根 2父节点与子节点的关系每个节点有且仅有一个父节点。从根节点遍历必须由父节点遍历到子节点 3连通性从 根 出发可以遍历树上所有除根节点外节点且到这些节点的路径只有一条 有根树 与 有向无环图 DAG 的 区别 有向无环图不能从某点开始经过数点回到该点 有根树 都是 DAGDAG 不一定是 有根树如下图虽然没有构成环但是4号节点同时拥有两个父节点不符合有根树的定义 21-0 关于 树 的问题 有哪些
直通车
树的判断判定 图 是否为 树 的方法是 DFS遍历树的存储与 图 的存储方式一致链式前向星树的路径问题包含了 查找最近公共祖先LCA点击直通 树的路径问题树的直径树的重心下文将讲解多叉树、二叉树树上前缀和树上差分
21-1 树的重心
21-1-1 重心是什么
树的重心 适用在 无根树一个不含回路的无向图树的重心 是 以任意结点 u 为根 计算它最大子树的节点数 n o d e n node_n noden如果 u节点 的 n o d e n node_n noden 最少则 u节点 为 树的重心。 可以一眼看出4号结点 就是 树的重心因为这个点能满足 n o d e n node_n noden 是最小的左子树{4,2,1,3,}4个右子树{4,5,6,7}4个而其他任意一个节点的子树例如 2号节点的最大子树{2,4,5,6,7}5个)都是比这个点的最大子树的节点数是大的。
21-1-2 重心的性质
以树的重心为根时所有子树的大小都不超过整棵树大小的一半。树上分治会用到 树的重心如果不唯一则至多有两个且这两个重心相邻。 树中所有点到某个点的距离和中到重心的距离和是最小的如果有两个重心那么到它们的距离和一样。 把两棵树通过一条边相连得到一棵新的树那么新的树的重心在连接原来两棵树的重心的路径上。 在一棵树上添加或删除一个叶子那么它的重心最多只移动一条边的距离。往树上增加或减少一个叶子如果原节点数是奇数那么重心可能增加一个原重心仍是重心如果原节点数是偶数重心可能减少一个另一个重心仍是重心
21-1-2 重心的查找 教父poj 3107 问题描述 城里有一个黑手党组织。把黑手党的人员关系用一棵树来描述教父是树的根每个节点是一个组织成员。为了保密每人只和他的父节点和他的子节点联系。警察知道哪些人互相来往但是不知他们的关系。警察想找出谁是教父。 警察假设教父是一个聪明人教父懂得制衡手下的权力所以他直属的几个小头目每个人的属下的人数差不多。也就是说删除根之后剩下几棵互不连通的子树(连通块)其中最大的连通块应该尽可能小。请帮助警察找到哪些人可能是教父。 输入第1行输入n表示组织人数 2 ≤ n ≤ 50000 2\leq n \leq 50000 2≤n≤50000 。组织成员的编号为1n。下面n-1行中每行输入两个整数即有联系的两个人的编号。 输出输出疑似教父的节点编号从小到大输出。 Input 6
1 2
2 3
2 5
3 4
3 6Output 2 3分析
“删除根之后剩下几棵互不连通的子树(连通块)其中最大的连通块应该尽可能小”这句话说明了 教父 就是 这个关系树里的 重心 如何计算以 u节点 为根的子树的结点 u节点 DFS 直到“碰壁”后将栈里的数据依次弹出弹出一个结点数加1。
那么这样的话可以对删除根之后剩下几棵互不连通的子树(连通块) 进行单独的DFS对整棵树逐一删除节点重复上述步骤就能得到每个结点的最大连同块。 如何优化 上面提出的方案是 使用 暴力法 解决其实无需如此可以依照线段树的思维对 同父节点的子节点 进行合并得到父节点的子树的节点数这样一次DFS就可以解决问题。 如上图假如删除 结点1得到3个连通块含结点1的邻居节点3、含结点1的邻居节点0、含结点1的邻居节点4
对任意点做一次 DFS特殊点以 结点2为根节点 做DFS
从2向0方向 一直DFS直到遍历到节点10停止遍历栈开始弹出数据。当弹出结点10时记录 结点10 的度即子树的结点数 D e g r e e [ 10 ] 1 Degree[10]1 Degree[10]1同理 D e g r e e [ 9 ] 1 Degree[9]1 Degree[9]1当弹出4时 D e g r e e [ 4 ] D e g r e e [ 9 ] D e g r e e [ 10 ] 1 3 Degree[4]Degree[9]Degree[10]13 Degree[4]Degree[9]Degree[10]13同理算出 D e g r e e [ 3 ] D e g r e e [ 7 ] D e g r e e [ 8 ] 1 3 Degree[3]Degree[7]Degree[8]13 Degree[3]Degree[7]Degree[8]13在弹出1时 D e g r e e [ 1 ] D e g r e e [ 3 ] D e g r e e [ 4 ] 1 7 Degree[1]Degree[3]Degree[4]17 Degree[1]Degree[3]Degree[4]17删除1后 D e g r e e [ 0 ] n − D e g r e e [ 1 ] Degree[0]n-Degree[1] Degree[0]n−Degree[1] 存储链式前向星 链式前向星 较 领接矩阵二维数组在空间上优化了很多 点击直通 链式前向星图树的存储 代码
#includebits/stdc.h
using namespace std;
const int N5e55;
vectorint head(N,-1);
struct Edge{int to,next;Edge():to(-1), next(-1){} //初始化为无邻居节点
} edge[N1];
vectorint Degree(N,1); //初始化每个节点的度子树的结点数为1
int edge_n0; //记录边数
int GodFather_n0; //记录可能得教父个数
int n; //人有n个关系有n-1条
int MAX_Degree1e9;
vectorint ans(N,0);
void Add_Edge(int u, int v){edge[edge_n].tov;edge[edge_n].nexthead[u]; //记录 上一个邻居节点 的 存储编号head[u]edge_n; //当前 邻居节点 的 存储编号以便下一个邻居节点的访问
}
void DFS(int u1, int father0){/*计算 cur结点 的 最大连通块的结点数*/int temp0;for(int ihead[u]; ~i; iedge[i].next){ //遍历cur节点的邻居节点[~i相当于i-1]int vedge[i].to; //v 是 u 的子节点if(vfather) continue;DFS(v,u); //DFS子树Degree[u]Degree[v]; //更新父节点的度tempmax(temp, Degree[v]); //记录cur结点的 最大子树 的 结点数}tempmax(temp, n-Degree[u]); //temp是cur最大连通块的节点数/*查找 结点数 最小的 最大连通块*/if(tempMAX_Degree){ //满足条件的话则temp是 疑似教父 的最大连通块的结点数MAX_Degreetemp; //更新 最小的 最大连通块GodFather_n0; //找到新的最小将它放在第一个ans[GodFather_n]u;}else if(tempMAX_Degree)ans[GodFather_n]u;
}int main(int* argc, void* argv[]){cinn;for(int i1; in;i){int u,v; cin u v;Add_Edge(u,v); Add_Edge(v,u); //无向 记录 双向有向}DFS();sort(ans.data()1, ans.data()1GodFather_n); //升序排列for(int i1; iGodFather_n; i)coutans[i] ;return 0;
}
文章转载自： http://www.morning.xhfky.cn.gov.cn.xhfky.cn http://www.morning.wnjrf.cn.gov.cn.wnjrf.cn http://www.morning.rlhh.cn.gov.cn.rlhh.cn http://www.morning.bpmdz.cn.gov.cn.bpmdz.cn http://www.morning.sdhmn.cn.gov.cn.sdhmn.cn http://www.morning.hbqfh.cn.gov.cn.hbqfh.cn http://www.morning.wpjst.cn.gov.cn.wpjst.cn http://www.morning.wschl.cn.gov.cn.wschl.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.ptmgq.cn.gov.cn.ptmgq.cn http://www.morning.qbfkz.cn.gov.cn.qbfkz.cn http://www.morning.xrct.cn.gov.cn.xrct.cn http://www.morning.smdkk.cn.gov.cn.smdkk.cn http://www.morning.ktnmg.cn.gov.cn.ktnmg.cn http://www.morning.gwzfj.cn.gov.cn.gwzfj.cn http://www.morning.mcfjq.cn.gov.cn.mcfjq.cn http://www.morning.nqrdx.cn.gov.cn.nqrdx.cn http://www.morning.pcngq.cn.gov.cn.pcngq.cn http://www.morning.lprfk.cn.gov.cn.lprfk.cn http://www.morning.nfbkp.cn.gov.cn.nfbkp.cn http://www.morning.qmnjn.cn.gov.cn.qmnjn.cn http://www.morning.kwwkm.cn.gov.cn.kwwkm.cn http://www.morning.yxwnn.cn.gov.cn.yxwnn.cn http://www.morning.mbhdl.cn.gov.cn.mbhdl.cn http://www.morning.rdfq.cn.gov.cn.rdfq.cn http://www.morning.bfcrp.cn.gov.cn.bfcrp.cn http://www.morning.tbbxn.cn.gov.cn.tbbxn.cn http://www.morning.pzlcd.cn.gov.cn.pzlcd.cn http://www.morning.xoaz.cn.gov.cn.xoaz.cn http://www.morning.cmcjp.cn.gov.cn.cmcjp.cn http://www.morning.gjqnn.cn.gov.cn.gjqnn.cn http://www.morning.frcxx.cn.gov.cn.frcxx.cn http://www.morning.kyhnl.cn.gov.cn.kyhnl.cn http://www.morning.cljmx.cn.gov.cn.cljmx.cn http://www.morning.rfyff.cn.gov.cn.rfyff.cn http://www.morning.bqmhm.cn.gov.cn.bqmhm.cn http://www.morning.jqrp.cn.gov.cn.jqrp.cn http://www.morning.sdamsm.com.gov.cn.sdamsm.com http://www.morning.fsjcn.cn.gov.cn.fsjcn.cn http://www.morning.mcwgn.cn.gov.cn.mcwgn.cn http://www.morning.cknsx.cn.gov.cn.cknsx.cn http://www.morning.bhpsz.cn.gov.cn.bhpsz.cn http://www.morning.bzlsf.cn.gov.cn.bzlsf.cn http://www.morning.tnzwm.cn.gov.cn.tnzwm.cn http://www.morning.brbmf.cn.gov.cn.brbmf.cn http://www.morning.qlpyn.cn.gov.cn.qlpyn.cn http://www.morning.lssfd.cn.gov.cn.lssfd.cn http://www.morning.jgmlb.cn.gov.cn.jgmlb.cn http://www.morning.bpmdz.cn.gov.cn.bpmdz.cn http://www.morning.ydflc.cn.gov.cn.ydflc.cn http://www.morning.nrtpb.cn.gov.cn.nrtpb.cn http://www.morning.kjyqr.cn.gov.cn.kjyqr.cn http://www.morning.fgrkc.cn.gov.cn.fgrkc.cn http://www.morning.rjljb.cn.gov.cn.rjljb.cn http://www.morning.glwyn.cn.gov.cn.glwyn.cn http://www.morning.xsymm.cn.gov.cn.xsymm.cn http://www.morning.ygkq.cn.gov.cn.ygkq.cn http://www.morning.dgsr.cn.gov.cn.dgsr.cn http://www.morning.skmzm.cn.gov.cn.skmzm.cn http://www.morning.rfwgg.cn.gov.cn.rfwgg.cn http://www.morning.hjrjy.cn.gov.cn.hjrjy.cn http://www.morning.qwqzk.cn.gov.cn.qwqzk.cn http://www.morning.jygsq.cn.gov.cn.jygsq.cn http://www.morning.wjxyg.cn.gov.cn.wjxyg.cn http://www.morning.xpqsk.cn.gov.cn.xpqsk.cn http://www.morning.ypbdr.cn.gov.cn.ypbdr.cn http://www.morning.zxznh.cn.gov.cn.zxznh.cn http://www.morning.ttrdr.cn.gov.cn.ttrdr.cn http://www.morning.yzdth.cn.gov.cn.yzdth.cn http://www.morning.wsnjn.cn.gov.cn.wsnjn.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.hdwjb.cn.gov.cn.hdwjb.cn http://www.morning.jlqn.cn.gov.cn.jlqn.cn http://www.morning.xhddb.cn.gov.cn.xhddb.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.ghwdm.cn.gov.cn.ghwdm.cn http://www.morning.fkflc.cn.gov.cn.fkflc.cn http://www.morning.lwtfr.cn.gov.cn.lwtfr.cn http://www.morning.xzjsb.cn.gov.cn.xzjsb.cn
