首页 > 编程语言 >基环树算法总结

基环树算法总结

时间:2024-04-20 11:34:15浏览次数:26  
标签:总结 dp2 dp1 int 基环树 算法 这道题 dp

基环树算法总结

一、什么是基环树

基环树,顾名思义,有两个要素:环和树。

因此,基环树就是一棵树的一个节点,扩成一个环,做题时,多棵基环树组成的基环树森林,常以如下方式出现:

  1. 每个点只有一个出边。
  2. 每个点只有一个入边。
  3. 图中一共有 \(n\) 个点,\(n\) 条边。

那么,基环树类型的题目应该怎么做呢?

二、基环树怎么做

先来看看这道题:\([ZJOI2008]\) 骑士

此题和没有上司的舞会几乎一模一样,不一样的是,这道题是基环树。

考虑假如这道题在树上就会简单很多,那么我们就会发现,假如断掉环上的一条边,那么原来的基环树就变成了一棵树,树形 dp 即可。

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int n,m,a,h[N],w[N];
int to[N*2],nxt[N*2];
int vis[N],fa[N];
int q1[N],q2[N],l,r;
ll dp1[N],dp2[N],ans;
void add(int x,int y){
    to[++m]=y;
    nxt[m]=h[x];
    h[x]=m;
}void dp_(int x,int f,int rt){
    vis[x]=1;
    dp1[x]=0;
    dp2[x]=w[x];
    for(int i=h[x];i;i=nxt[i]){
        int y=to[i];
        if(y==a)
            continue;
        dp_(y,x,rt);
        dp1[x]+=max(dp1[y],dp2[y]);
        dp2[x]+=dp1[y];
    }
}int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int j;
        cin>>w[i]>>j;
        add(j,i);
        fa[i]=j;
    }for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        vis[(a=i)]=1;
        while(!vis[fa[a]]){
            a=fa[a];
            vis[a]=1;
        }dp_(a,0,a);
        ll cc=dp1[a];
        a=fa[a];
        dp_(a,0,a);
        ans+=max(cc,dp1[a]);
    }cout<<ans;
    return 0;
}

接着我再介绍一下我求基环树(单向图)时常用的找环方法(其中 \(a_i\) 表示 \(i\) 的出/入边与 \(a_i\) 相连):

在进行并查集时,无条件将 \(i\) 置于 \(a_i\) 下。这样可以保证每个根节点都在环上,使判环更便捷、更迅速。

标签:总结,dp2,dp1,int,基环树,算法,这道题,dp
From: https://www.cnblogs.com/chang-an-22-lyh/p/18147499/jhs_zj

相关文章

  • 掌握时间序列特征工程:常用特征总结与 Feature-engine 的应用
    时间序列数据的特征工程是一种技术,用于从时间序列数据中提取信息或构造特征,这些特征可用于提高机器学习模型的性能。以下是一些常见的时间序列特征工程技术:滚动统计量:计算时间窗口内的统计量,如平均值、中位数、标准偏差、最小值和最大值。这些统计量可以捕捉到时间序列在不同时......
  • 在路上阶段总结之反对本本主义
      今天把一个客户教育了。教育之后,发现自己被自己教育了。事情是这样的,客户提出来一个产品,让我评估一下工作量。我接连问了客户几个需求方面的问题。发现该客户一脸懵逼,他对自己规划的产品根本没什么深入了解。不懂市场定位,不懂具体的技术风险。反正就是只有一个想法,就是,所有......
  • OOP题目集1~3的总结
    目录(一)前言(二)作业介绍(三)算法与代码(四)SourceMonitor代码分析(五)自学内容(六)总结一、前言介绍本篇博客的大致内容、写作目的、意义等本篇博客介绍如何使用Java语言基础和算法来解决题目问题,在此基础上进行对最近Java编程语言学习的总结题目的难度为Java入门,主要考察类......
  • 31天【代码随想录算法训练营34期】第八章 贪心算法 part01(● 理论基础 ● 455.分发
    贪心算法就是先选局部最优,再推全局最优没有套路将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解●455.分发饼干classSolution:deffindContentChildren(self,g:List[int],s:List[int])->int:g.s......
  • 人间算法题:到底是不是一个环?
    很多人都说人生就是一个循环,每天重复重复。而所谓环,对于写代码的小伙伴来说是有特殊定义的。我的理解就是节点循环,就成了环。刚好刷到一个掘金好友分享的腾讯一面算法题:判断一个单链表是不是一个环。其实有很多办法来实现,但是我更喜欢用快慢指针来判断环的形成。思路如下:定义......
  • 行人属性AI识别/人体结构化属性AI识别算法的原理及应用场景介绍
    行人属性AI识别技术是一种基于人工智能技术的图像识别技术,通过对行人的图像或视频进行处理和分析,提取出其中的结构化信息,如人体姿态、关键点位置、行人属性(性别、年龄、服装等)等。行人结构化数据分析的方法包括姿态估计、关键点检测、行人属性识别等:姿态估计是指根据行人的姿势......
  • linux运维常用命令总结
    1.tarzcf打包目录时,排除其中的一些目录或者文件tar--exclude=dir1--exclude=dir2--exclude=file1-czvfarchive.tar.gzsource_directory 2.yum只下载不安装包yum-yinstallnfs-utilsrpcbind--downloadonly--downloaddir/home/nfs 3.查看本机出网IP地址......
  • SPFA算法
    单源最短路算法,可以处理负边权,平均时间复杂度\(O(kn)\),最坏时间复杂度\(O(mn)\)问题描述:有一个连通图\(G=(V,E)\),连接节点\(i\)和节点\(j\)的边权写作\(e^i_j\)(\(e^i_j\geq0\)),求从起点(\(s,s\inV\))开始,到其它各个节点(\(d,d\inV-s\))的最短路长度。思路详解:设从起点s到节点d......
  • yolo,rcnn,fastrcnn,ssd等算法有的区别
    chatgpt回答:YOLO(YouOnlyLookOnce),RCNN(Region-basedConvolutionalNeuralNetworks),FasterR-CNN,SSD(SingleShotMultiBoxDetector)等算法都是用于目标检测的经典算法,它们在实现目标检测任务时有一些区别。YOLO:YOLO是一种单阶段(single-stage)目标检测算......
  • 30 天精通 RxJS (25):Subject 总结
    Subject其实在RxJS中最常被误解的一部份,因为Subject可以让你用命令式的方式虽送值到一个observable的串流中。很多人会直接把这个特性拿来用在不知道如何建立Observable的状况,比如我们在30天精通RxJS(23)中提到的可以用在ReactJS的Event中,来建立event的observab......