• <menu id="w8222"></menu>
    <object id="w8222"><u id="w8222"></u></object>
  • <input id="w8222"><u id="w8222"></u></input><input id="w8222"><acronym id="w8222"></acronym></input>
    <menu id="w8222"><u id="w8222"></u></menu>
  • <menu id="w8222"></menu>
  • 基环树略解

    基环树

    基环树,也叫 环套树,是一种图的类型。如果连通图 \(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\) 个人中选出若干个人,使他们讨厌的人没被选中,且他们的战斗力之和最大。

    总结

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

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

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

    相关文章
    相关标签/搜索
    2020今天开什么码特2018香港开奖结果 2018年六给彩今晚开奖结果 2018六开彩开奖结果 六合彩开奖结果 锡林浩特市| 布尔津县| 嘉鱼县| 望江县| 甘南县| 临安市| 珲春市| 天等县| 盱眙县| 东莞市| 揭阳市| 同仁县| 北宁市| 镇平县| 县级市| 边坝县| 遂溪县| 湖口县| 彩票| 佛冈县| 伊金霍洛旗| 吐鲁番市| 孟连| 许昌县| 定安县| 巍山| 高青县| 团风县| 安义县| 渝北区| 全南县| 郯城县| 永善县| 长沙市| 壶关县| 大英县| 凤山市| 宜春市| 韩城市| 客服| 茂名市| 阳江市| 余干县| 襄汾县| 吉林省| 葫芦岛市| 柘城县| 蓝山县| 天镇县| 永修县| 南汇区| 洪江市| 龙里县| 大关县| 大竹县| 佛山市| 黄梅县| 浦城县| 雅安市| 云霄县| 伊宁市| 电白县| 北川| 阿鲁科尔沁旗| 甘洛县| 福建省| 富源县| 施秉县| 元江| 襄城县| 蕉岭县| 太康县| 扎兰屯市| 水城县| 博罗县| 大丰市| 三河市| 惠来县| 白银市| 中牟县| 漳浦县| 那坡县| 西吉县| 中超| 南汇区| 夏邑县| 石景山区| 广水市| 高青县| 林西县| 酒泉市| 凤翔县| 陵水| 平利县| 丹江口市| 淮滨县| 阿勒泰市| 延安市| 大同市| 定陶县| 花垣县| 屏山县| 蓬莱市| 河津市| 剑河县| 新乡市| 克拉玛依市| 沽源县| 泾川县| 宜兴市| 双牌县| 蚌埠市| 乐山市| 兴义市| 施甸县| 揭西县| 江津市| 花垣县| 郓城县| 靖江市| 鸡泽县| 德格县| 万载县| 永登县| 荔浦县| 南溪县| 南溪县| 比如县| 丽江市| 锦州市| 绥化市| 五莲县| 泗洪县| 原平市| 丹寨县| 岑巩县| 洞头县| 额济纳旗| 获嘉县| 博野县| 凤山县| 虹口区| 镇赉县| 夹江县| 登封市| 萝北县| 康平县| 无锡市| 左权县| 洛南县| 汉寿县| 弋阳县| 芜湖县| 木里| 华安县| 湄潭县| 乌鲁木齐市| 新干县| 弥渡县| 全南县| 日喀则市| 拉孜县| 大方县| 澄江县| 永丰县| 乌兰察布市| 浦北县| 宁国市| 沧州市| 广元市| 左云县| 普格县| 饶阳县| 江北区| 保定市| 景德镇市| 上杭县| 新兴县| 古丈县| 合作市| 德兴市| 广西| 翼城县| 平南县| 青冈县| 隆子县| 鄂尔多斯市| 海晏县| 扶沟县| 凯里市| 台南县| 大港区| 昌图县| 建平县| 襄垣县| 延边| 慈溪市| 隆林| 双辽市| 阿坝县| 冀州市| 尤溪县| 苗栗市| 和龙市| 中江县| 西昌市| 麻城市| 道孚县| 博野县| 额济纳旗| 安岳县| 宁海县| 宣化县| 保山市| 老河口市| 宣汉县| 安泽县| 兖州市| 东阳市| 桐柏县| 呼图壁县| 女性| 乐山市| 开阳县| 盐亭县| 定南县| 吉林市| 鸡西市| 吕梁市| 临夏市| 荥阳市| 抚顺市| 盐津县| 周宁县| 小金县| 紫阳县| 启东市| 白玉县| 商都县| 右玉县| 云和县| 淮安市| 松原市| 水富县| 石首市| 常山县| 昌江| 诸暨市| 城固县| 武邑县| 琼海市| 肃南| 会同县| 靖远县| 宁波市| 桓台县| 珠海市| 仁怀市| 修文县| 新宁县| 缙云县| 临漳县| 仁布县| 汉川市| 北辰区| 沙洋县| 海城市| 永福县| 台州市| 商城县| 贡嘎县| 兰坪| 龙州县| 年辖:市辖区| 金川县| 南宁市| 高安市| 台安县| 慈溪市| 东源县| 凌海市| 华坪县| 库伦旗| 永春县| 桃江县| 利川市| 连平县| 岳阳县| 从化市| 益阳市| 山东省| 龙胜| 登封市| 平度市| 迁西县| 大足县| 山阴县| 察隅县| 垦利县| 静宁县| 盘锦市| 云安县| 苗栗市| 乌什县| 和硕县| 泽库县| 清原| 平阴县| 长乐市| 卓资县| 民丰县| 西充县| 永泰县| 壤塘县| 乐东| 土默特右旗| 鄂托克旗| 阿拉尔市| 泗阳县| 德化县| 集贤县| 永嘉县| 即墨市| 东明县| 蕉岭县| 高青县| 信宜市| 涡阳县| 黔西| 沙洋县| 吉林省| 凯里市| 金湖县| 株洲县| 永顺县| 昌宁县| 吴忠市| 灌云县| 新泰市| 海安县| 洪洞县| 玉树县| 贺州市| 惠安县| 宁城县| 奇台县| 富民县| 渝中区| 上虞市| 祥云县| 浑源县| 新宁县| 来凤县| 沙田区| 高邑县| 姜堰市| 福清市| 明溪县| 呼图壁县| 南宫市| 武威市| 长沙市| 嘉义县| 潍坊市| 都匀市| 石景山区| 海伦市| 信阳市| 日喀则市| 金山区| 夏邑县| 信阳市| 南昌市| 武平县| 靖宇县| 鹿泉市| 佛坪县| 扶沟县| 开化县| 航空| 宁阳县| 富蕴县| 晋城| 拜泉县| 久治县| 哈尔滨市| 南京市| 左权县| 湖南省| 株洲市| 枝江市| 莫力| 白山市| 阜新| 东阿县| 左权县| 临沧市| 乌兰浩特市| 日土县| 淮安市| 乐业县| 房产| 石家庄市| 五莲县| 鄂温| 岐山县| 皮山县| 镇坪县| 甘肃省| 酒泉市| 大邑县| 额尔古纳市| 太仆寺旗| 民乐县| 社旗县| 平泉县| 郁南县| 斗六市| 镇平县| 北宁市| 沂水县| 泸水县| 阿克苏市| 巩留县| 轮台县| 土默特右旗| 荆州市| 连江县| 教育| 彝良县| 龙井市| 乌拉特中旗| 房产| 万载县| 于田县| 兰溪市| 瑞金市| 易门县| 九龙城区| 葫芦岛市| 文成县| 西乌珠穆沁旗| 衡阳市| 利津县| 九台市| 莫力| 伊川县| 靖安县| 阿瓦提县| 郎溪县| 洱源县| 辽中县| 富蕴县| 桐庐县| 茂名市| 乐业县| 琼海市| 施甸县| 宁明县| 宣汉县| 祥云县| 得荣县| 龙南县| 营口市| 昭苏县| 铜陵市| 宜宾市| 容城县| 华宁县| 扬州市| 黄石市| 津南区| 丰镇市| 乌海市| 白水县| 工布江达县| 景洪市| 马龙县| 古丈县| 兴国县| 土默特左旗| 英吉沙县| 沙洋县| 墨玉县| 泰州市| 柳江县| 恭城| 东阳市| 湘乡市| 宜章县| 凤冈县| 平南县| 岳池县| 岗巴县| 长顺县| 波密县| 四川省| 彭泽县| 方山县| 水城县| 翁牛特旗| 陆河县| 石家庄市| 三穗县| 新竹县| 务川| 汤阴县| 榕江县| 宣威市| 名山县| 雅安市| 嘉黎县| 蓬溪县| 社旗县| 望奎县| 拉萨市| 句容市| 拜城县| 麻城市| 屯门区| 桂平市| 巨野县| 汶川县| 新民市| 浦北县| 芦山县| 永胜县| SHOW| 墨竹工卡县| 黄大仙区| 平凉市| 浦北县| 宜黄县| 普陀区| 阳曲县| 乐至县| 长汀县| 南漳县| 如皋市| 台湾省| 澄江县| 南昌县| 堆龙德庆县| 三都| 佛学| 吐鲁番市| 二手房| 夹江县| 邵东县| 黄浦区| 双江| 崇仁县| 尉犁县| 北碚区| 土默特左旗| 武定县| 通州市| 遵义市| 融水| 英超| 和田市| 邢台市| 阿勒泰市| 赤峰市| 宁安市| 鲁山县| 托克托县| 九龙城区| 阿勒泰市| 花垣县| 辛集市| 弥勒县| 成武县| 萨嘎县| 霸州市| 于都县| 沙坪坝区| 长乐市| 内乡县| 固镇县| 东乌珠穆沁旗| 余干县| 淮安市| 朔州市| 眉山市| 明溪县| 巴塘县| 固镇县| 囊谦县| 长乐市| 望谟县| 山阳县| 孟连| 旅游| 方山县| 赣榆县| 应用必备| 揭西县| 昌乐县| 崇阳县| 上饶市| 友谊县| 博乐市| 肥城市| 广宗县| 彭州市| 靖宇县| 南雄市| 镇沅| 桐乡市| 泌阳县| 高州市| 忻城县| 雅江县| 永兴县| http://www.bm1961xoonz.fit http://hbdwwo.fit http://otkavd.fit http://www.pfyicj.fit http://www.yooovs.fit http://wap.uqeoxi.fit http://wap.pcxgyp.fit http://tvtawp.fit http://wap.yooovs.fit http://upfgmz.fit http://wap.jtrvfn.fit http://tlwbxa.fit http://wap.vveufs.fit http://ertnzz.fit http://m.bxvtyu.fit http://sjddrn.fit http://m.vtbaet.fit http://wap.dimwjp.fit