<menu id="gc4q0"></menu>
  • <menu id="gc4q0"></menu>
  • <input id="gc4q0"></input>
    <nav id="gc4q0"></nav>
  • <input id="gc4q0"><acronym id="gc4q0"></acronym></input>
  • 基环树略解

    基环树

    基环树,也叫 环套树,是一种图的类型。如果连通图 \(G=\{V,E\}\)\(|V|=|E|\),则我们称它是基环树。

    顾名思义,基环树就好似是在一棵树上加一条边得到的图。基环树有且仅有一个环,所以也被成为环套树。
    在这里插入图片描述
    如上图所示的图就是一棵基环树。

    用途

    基环树没什么用。

    它只能解决部分特殊问题,而这类问题通常会注明“边数=点数”,解法也比较单一,常被与其他算法一同考察。

    我们来看几道例题。


    luogu P1453 城市环路)今有基环树 \(G=\{V,E\}\),定义\[ans=\sum_{i=1}^{N}{a_i·b_i}\]\(\forall i\in[1,N]∩\N^*\)\(b_i\in\{0,1\}\),且 \(\forall e=(u,v)\in E\)\(b_u\text{ and }b_v=0\)\(\text{and}\) 表示按位与运算)。求 \(ans_{\max}\)

    Solution 本题中如果 \(N=M+1\),这显然就是“没有上司的舞会”了。

    考虑将新问题转化成已解决的问题。我们发现,环上有且仅有一条边对计算不产生影响,删除它即可。由一条边上的两个点不能被同时选中,不难想到给每个点设置两个状态:选中(1)与不选中(0);并查集找环,删除一条边后做树形动态规划即可解决此题。时间复杂度 \(O(N\alpha(N))\)

    参考代码

    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    
    const int MAXN=100010;
    
    int fa[MAXN];
    int a[MAXN];
    int sx,sy,fx,fy;
    int ST,ED;
    int n;
    
    struct node{
        int x,y,next;
    }e[MAXN+MAXN];
    int len=0;
    int first[MAXN];
    int ans;
    int f[MAXN][3];
    
    
    int findfa(int x){
        if(x==fa[x]) return x;
        return fa[x]=findfa(fa[x]);
    }
    void ins(int x,int y){
        e[++len].x=x;e[len].y=y;
        e[len].next=first[x];first[x]=len;
    }
    int max(int x,int y){
        return x>y?x:y;
    }
    void dfs(int x,int last){
        f[x][1]=a[x];f[x][0]=0;
        for(int i=first[x];i;i=e[i].next){
            int y=e[i].y;
            if(y==last) continue;
            dfs(y,x);
            f[x][0]+=max(f[y][1],f[y][0]);
            f[x][1]+=f[y][0];
        }
    }
    inline int read(){
        int x=0; char c;
        do c=getchar(); while(c<'0'||c>'9');
        while(c>='0'&&c<='9')
            x=x*10+c-48,c=getchar();
        return x;
    }
    int main(){
        n=read();
        for(int i=1;i<=n;++i){
            a[i]=read();
            fa[i]=i;
        }
        memset(first,0,sizeof(first));
        for(int i=1;i<=n;++i){
            sx=read()+1;sy=read()+1;
            fx=findfa(sx);fy=findfa(sy);
            if(fx==fy){
                ST=sx;ED=sy;
                continue;
            }
            ins(sx,sy);ins(sy,sx);
            fa[fx]=fy;
        }
        memset(f,0,sizeof(f));
        dfs(ST,0);ans=f[ST][0];
        dfs(ED,0);ans=max(ans,f[ED][0]);
        double k;
        scanf("%lf",&k);
        printf("%.1lf",ans*k);
    }

    接下来的这道习题与例题的思路不太一样。

    练习 1[NOIp2018] luogu P5022 旅行)有一棵基环树 \(T\),你初始在一个点上。每次可以从下列选项中选择一项执行:

    1. 沿着一条边走到一个没有访问过的点;
    2. 沿着一条边返回一个访问过的点。

    你需要依此法访问所有的 \(N\) 个点。每个点被首次访问的顺序形成了一个序列,求这个序列字典序最小的那个。

    基环树的建图同样重要。
    练习 2luogu P2607 [ZJOI2008]骑士)有 \(N\) 个人,每个人有两个值:\(d_i\) 战斗力,\(t_i\) 讨厌的人的编号(\(t_i\neq i\))。从这 \(N\) 个人中选出若干个人,使他们讨厌的人没被选中,且他们的战斗力之和最大。

    总结

    基环树的初步内容较少,解法单一,经常与其他算法一同出现。

    解决基环树上问题的关键点就是:处理额外边,将原问题转化成树上问题。

    本文列举了两种处理额外边的方法,难免有所疏漏敬请指正。此外,如果读者有好题推荐可以在评论区留言,我会尽量回复。感谢阅读。

    相关文章
    相关标签/搜索
    香港最快現场开奖结果118图库天下彩天空彩免费大全香港蓝月亮精选资料六合宝典天天彩票新版 荔浦县| 普洱| 平安县| 汉川市| 澄城县| 彝良县| 普兰县| 伊宁县| 萨迦县| 五指山市| 孙吴县| 吉安市| 乌苏市| 新乡市| 探索| 雅安市| 五原县| 临朐县| 扎囊县| 崇义县| 贺州市| 隆尧县| 太仆寺旗| 贡嘎县| 淮安市| 岐山县| 土默特左旗| 安新县| 义乌市| 舒兰市| 新密市| 成都市| 抚州市| 南靖县| 香河县| 介休市| 安宁市| 辽阳市| 桂林市| 清丰县| 琼中| 五指山市| 离岛区| 肥城市| 新津县| 鄂州市| 呼和浩特市| 钟祥市| 界首市| 奎屯市| 曲阜市| 永清县| 宁化县| 灵川县| 临潭县| 邢台县| 汤原县| 琼中| 子长县| 赤壁市| 安乡县| 大洼县| 玉龙| 安化县| 安多县| 彰武县| 广宁县| 贺兰县| 淮南市| 临沂市| 新建县| 永康市| 广丰县| 开化县| 高碑店市| 含山县| 汉川市| 兴城市| 陕西省| 曲沃县| 平顶山市| 漳浦县| 扬州市| 永吉县| 长岛县| 海盐县| 福清市| 萝北县| 景洪市| 黑水县| 安远县| 长子县| 沙坪坝区| 蒙阴县| 利辛县| 襄樊市| 阳城县| 泽州县| 卓资县| 延边| 阳泉市| 板桥市| 晋宁县| 莒南县| 南和县| 宜州市| 蒙城县| 开封市| 夏邑县| 洪泽县| 遂平县| 尉氏县| 峡江县| 通道| 通榆县| 成武县| 桃园县| 灵台县| 茌平县| 简阳市| 芷江| 建德市| 象山县| 涡阳县| 吴桥县| 精河县| 河西区| 景泰县| 堆龙德庆县| 成安县| 潞西市| 虹口区| 海丰县| 北票市| 东明县| 沅江市| 巧家县| 万山特区| 永年县| 阿克| 卫辉市| 陵川县| 沿河| 石屏县| 二连浩特市| 镇坪县| 睢宁县| 盐亭县| 汶上县| 沐川县| 江北区| 雷山县| 丰顺县| 铜鼓县| 滨海县| 石家庄市| 炎陵县| 龙山县| 山阴县| 沈丘县| 额敏县| 宝坻区| 连山| 太和县| 南城县| 江陵县| 中卫市| 称多县| 古蔺县| 资溪县| 肃宁县| 曲水县| 蚌埠市| 江安县| 五大连池市| 宁晋县| 临猗县| 五河县| 深州市| 叶城县| 墨脱县| 吴忠市| 赤壁市| 天镇县| 云浮市| 平和县| 道真| 岚皋县| 孟州市| 铜梁县| 陇南市| 新巴尔虎左旗| 会昌县| 东方市| 井研县| 延津县| 古田县| 康平县| 改则县| 方城县| 岳西县| 宁晋县| 谷城县| 崇左市| 礼泉县| 富川| 田阳县| 桃源县| 岐山县| 龙门县| 凤庆县| 兴文县| 淮北市| 蓝山县| 邢台县| 罗源县| 遵义县| 敦煌市| 盖州市| 珲春市| 长汀县| 吉水县| 朝阳县| 新昌县| 上蔡县| 泗水县| 漳平市| 东乡族自治县| 大方县| 崇仁县| 柳州市| 娱乐| 冕宁县| 平安县| 武川县| 河东区| 米泉市| 贞丰县| 崇仁县| 如东县| 海原县| 盐源县| 阜南县| 中江县| 年辖:市辖区| 开阳县| 徐水县| 麻栗坡县| 永登县| 西林县| 中方县| 汝州市| 定兴县| 安丘市| 冀州市| 武汉市| 尉犁县| 浏阳市| 织金县| 萨迦县| 渝中区| 封开县| 松阳县| 承德市| 县级市| 南城县| 白水县| 虹口区| 峨边| 故城县| 塔河县| 会东县| 望都县| 庆安县| 灌阳县| 晴隆县| 嵩明县| 百色市| 汝州市| 呼伦贝尔市| 泰顺县| 峨山| 苏尼特左旗| 吴旗县| 南开区| 阜城县| 诸城市| 仲巴县| 巴楚县| 双柏县| 那曲县| 防城港市| 平远县| 赤壁市| 武城县| 包头市| 油尖旺区| 泌阳县| 石林| 星座| 缙云县| 海丰县| 长岭县| 景德镇市| 鲁山县| 桂林市| 瓮安县| 黎平县| 普宁市| 武冈市| 修水县| 博乐市| 罗田县| 壶关县| 中牟县| 刚察县| 望奎县| 资兴市| 日土县| 石楼县| 定南县| 荥阳市| 安仁县| 尉犁县| 延川县| 呈贡县| 增城市| 柳河县| 镇坪县| 岳阳县| 台东市| 合山市| 宣武区| 合肥市| 卢氏县| 大洼县| 上饶市| 高州市| 临桂县| 雷山县| 霍城县| 绥江县| 阳东县| 龙泉市| 漾濞| 武义县| 赤水市| 鸡东县| 大竹县| 神池县| 济南市| 防城港市| 含山县| 昆山市| 黎川县| 邵武市| 长丰县| 茌平县| 嵊州市| 博客| 界首市| 江华| 峨边| 出国| 海淀区| 乃东县| 尚志市| 长子县| 庄河市| 铜陵市| 阿鲁科尔沁旗| 安化县| 泸州市| 曲阜市| 江都市| 唐山市| 蕉岭县| 于田县| 云霄县| 合作市| 邵武市| 通渭县| 武乡县| 凌源市| 颍上县| 公主岭市| 阜城县| 溧水县| 苏尼特左旗| 睢宁县| 民和| 台北市| 凤庆县| 连平县| 枣庄市| 轮台县| 闸北区| 德保县| 东阿县| 墨脱县| 乡宁县| 建德市| 莱芜市| 孝感市| 伊吾县| 手游| 辰溪县| 星子县| 耿马| 安福县| 清水河县| 安阳县| 岫岩| 堆龙德庆县| 鄂伦春自治旗| 息烽县| 乡城县| 武山县| 拜城县| 湟中县| 依兰县| 星子县| 五莲县| 新蔡县| 福建省| 连江县| 新和县| 东兰县| 海伦市| 昌宁县| 高碑店市| 铜陵市| 延长县| 杭锦后旗| 临江市| 邵武市| 新巴尔虎右旗| 龙海市| 牡丹江市| 化德县| 苗栗县| 安龙县| 通城县| 平定县| 剑阁县| 清河县| 洛宁县| 永登县| 襄城县| 大姚县| 孟村| 尼玛县| 聂拉木县| 新竹县| 涿鹿县| 大连市| 聂荣县| 大英县| 株洲市| 白城市| 延寿县| 沅陵县| 怀仁县| 蓬安县| 平罗县| 张北县| 余干县| 兴安县| 潮州市| 日喀则市| 正定县| 黎川县| 青田县| 乌海市| 寿阳县| 腾冲县| 东阳市| 东乌珠穆沁旗| 乌审旗| 古浪县| 罗源县| 府谷县| 青田县| 徐闻县| 奎屯市| 容城县| 鄂托克前旗| 襄樊市| 赤壁市| 芜湖县| 木兰县| 和龙市| 中超| 东兰县| 峡江县| 睢宁县| 营口市| 南华县| 浦江县| 乐至县| 连山| 武强县| 达拉特旗| 乐亭县| 通州区| 华池县| 屏山县| 平舆县| 乡宁县| 米林县| 清丰县| 陵水| 张家界市| 运城市| 德昌县| 望奎县| 丰顺县| 平谷区| 牡丹江市| 雅安市| 大足县| 巴楚县| 太仆寺旗| 双鸭山市| 永春县| 德兴市| 永济市| 乌恰县| 虞城县| 逊克县| 赫章县| 定陶县| 定兴县| 钟山县| 保定市| 贞丰县| 北川| 子长县| 关岭| 晋城| 库尔勒市| 仲巴县| 保靖县| 莆田市| 高阳县| 镇坪县| 永定县| 青海省| 崇义县| 两当县| 如皋市| 长顺县| 北宁市| 冷水江市| 富民县| 和硕县| 大化| 长白| 平罗县| 泸西县| 冷水江市| 南召县| 林口县| 西城区| 株洲县| 汾阳市| 新建县| 宜川县| 高阳县| 平原县| 马关县| 定边县| 拉萨市| 延川县| 哈巴河县| 元朗区| 平果县| 双城市| 松桃| 江北区| 广饶县| 乐亭县| 灵宝市| 蒙自县| 鸡西市| 广东省| 鄂托克旗| 古田县| 长沙县| 北海市| 元谋县| 兴文县| 遂溪县| 新野县| 黄梅县| 巩义市| 清水河县| 黔西| 鹤峰县| 玉树县| 五大连池市| 普兰县| 泉州市| 茶陵县| 山阳县| 健康| 青田县| 漯河市| 含山县| 平泉县| 赞皇县| 正宁县| 忻城县| 东乡县| 兴和县| http://m.jx1870cablev.fun http://m.jx1870becozev.fun http://m.jx1870budgetv.fun http://m.jx1870copyv.fun http://wap.jx1870cleanv.fun http://wap.jx1870briefv.fun http://3g.jx1870castv.fun http://wap.jx1870claizv.fun http://m.jx1870deterzinev.fun http://m.jx1870catalogv.fun http://jx1870accessv.fun http://m.jx1870basev.fun http://wap.jx1870downloadv.fun http://3g.jx1870cruisev.fun http://www.jx1870drugv.fun http://m.jx1870addressv.fun http://m.jx1870earnv.fun http://wap.jx1870createv.fun