基环树略解

        基环树

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

        总结

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

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

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

        相关文章
        相关标签/搜索
        香港最快現场开奖结果4887王中王鉄算 盘开奖结果2019开奖结果,香港马会资枓大全2019,管家婆王中王鉄算盘开奖结果 禄丰县| 仁寿县| 宁城县| 汾西县| 乐陵市| 平安县| 长武县| 阜新| 孙吴县| 秭归县| 浪卡子县| 得荣县| 灵宝市| 灵山县| 比如县| 繁峙县| 唐海县| 刚察县| 墨玉县| 武鸣县| 安乡县| 阳江市| 芦山县| 罗田县| 鄂托克前旗| 定陶县| 闻喜县| 井陉县| 确山县| 军事| 上犹县| 扬州市| 闽清县| 都安| 桑植县| 姜堰市| 运城市| 牟定县| 祁连县| 彭水| 陕西省| 南召县| 安图县| 云安县| 苏尼特右旗| 柘荣县| 竹北市| 西昌市| 海南省| 米脂县| 彭泽县| 黄龙县| 和静县| 武清区| 新蔡县| 罗山县| 商丘市| 平原县| 诏安县| 文安县| 阳春市| 长葛市| 商水县| 锡林郭勒盟| 南城县| 张掖市| 元氏县| 徐州市| 湖口县| 浮山县| 新巴尔虎右旗| 岱山县| 山阴县| 锦州市| 苗栗县| 洪洞县| 绥德县| 凌云县| 新绛县| 石渠县| 壶关县| 招远市| 茶陵县| 岳池县| 潮州市| 西宁市| 扶风县| 津市市| 章丘市| 康保县| 京山县| 白银市| 平遥县| 井冈山市| 乐陵市| 绥宁县| 皮山县| 德令哈市| 会泽县| 武宣县| 虎林市| 靖江市| 武乡县| 海原县| 茶陵县| 台北县| 黄平县| 吉木乃县| 深州市| 洪泽县| 石城县| 祁东县| 贞丰县| 望城县| 云梦县| 广丰县| 宜阳县| 莱西市| 库尔勒市| 宜兴市| 吴堡县| 盐亭县| 东港市| 克拉玛依市| 新郑市| 华坪县| 西贡区| 卓资县| 抚州市| 安平县| 乡城县| 甘泉县| 盐亭县| 德江县| 饶河县| 呼和浩特市| 陈巴尔虎旗| 准格尔旗| 华安县| 西昌市| 深州市| 博爱县| 类乌齐县| 自治县| 剑河县| 邯郸县| 安新县| 邻水| 哈巴河县| 湛江市| 泽州县| 华蓥市| 海伦市| 通辽市| 沾益县| 宜春市| 合作市| 乌拉特前旗| 定日县| 海淀区| 永年县| 阳原县| 永济市| 绥化市| 霍林郭勒市| 黄浦区| 铜山县| 民乐县| 闽清县| 中宁县| 郯城县| 亚东县| 新沂市| 安阳市| 增城市| 平顶山市| 伊春市| 刚察县| 西畴县| 揭东县| 峡江县| 武邑县| 新兴县| 莒南县| 平泉县| 中牟县| 高台县| 馆陶县| 固始县| 八宿县| 清苑县| 南投市| 博野县| 清苑县| 同德县| 临夏县| 田林县| 牙克石市| 万源市| 河北区| 武宣县| 新巴尔虎左旗| 通山县| 新绛县| 隆昌县| 乌鲁木齐县| 韶关市| 曲阜市| 新安县| 丰原市| 红桥区| 仁布县| 安顺市| 独山县| 白朗县| 永顺县| 靖远县| 滁州市| 平昌县| 泊头市| 桐乡市| 防城港市| 罗田县| 宜州市| 正阳县| 萍乡市| 乐陵市| 大余县| 民县| 东源县| 无极县| 寿光市| 临漳县| 邵武市| 屯留县| 嵊州市| 汕尾市| 儋州市| 武定县| 剑川县| 辽阳县| 特克斯县| 嘉禾县| 宁安市| 青海省| 桑植县| 秦皇岛市| 凌海市| 芦溪县| 霍城县| 大同市| 吴江市| 安新县| 磴口县| 昌黎县| 土默特左旗| 铅山县| 黄骅市| 巴中市| 平远县| 武强县| 彝良县| 鹿邑县| 泊头市| 芒康县| 修水县| 科技| 华亭县| 额尔古纳市| 定陶县| 灌南县| 合肥市| 平和县| 大竹县| 泸溪县| 多伦县| 关岭| 徐州市| 称多县| 寻乌县| 车致| 林甸县| 西林县| 尼玛县| 乌鲁木齐市| 乳山市| 旬邑县| 郁南县| 团风县| 东安县| 周口市| 达州市| 扬中市| 叶城县| 泰州市| 清涧县| 灯塔市| 凤凰县| 广南县| 乌拉特前旗| 巧家县| 抚远县| 霍邱县| 延安市| 麟游县| 绥滨县| 阿巴嘎旗| 昭通市| 平江县| 辽中县| 故城县| 宾川县| 石台县| 察哈| 鄯善县| 桦南县| 祁东县| 海丰县| 隆子县| 四川省| 南丹县| 垣曲县| 黔南| 新宁县| 南丰县| 肃南| 定西市| 通城县| 延寿县| 台江县| 西乌珠穆沁旗| 双流县| 门源| 瓮安县| 宁蒗| 九龙坡区| 潮州市| 阳新县| 巴塘县| 万宁市| 寿光市| 黄梅县| 定远县| 屏东县| 上蔡县| 奉化市| 班戈县| 沭阳县| 旺苍县| 临城县| 会昌县| 肇庆市| 信阳市| 正安县| 兴业县| 泌阳县| 将乐县| 怀来县| 博乐市| 渝中区| 怀宁县| 清水县| 成武县| 科技| 夏河县| 金坛市| 福州市| 桂平市| 华阴市| 航空| 云阳县| 昌乐县| 固镇县| 衢州市| 基隆市| 安龙县| 平邑县| 乌鲁木齐县| 民乐县| 汕头市| 韩城市| 乌什县| 鹤岗市| 竹山县| 金沙县| 耿马| 贡山| 内江市| 南溪县| 黄平县| 临清市| 阿巴嘎旗| 陇南市| 儋州市| 和林格尔县| 三原县| 天门市| 大同县| 乐陵市| 碌曲县| 苏尼特左旗| 祁东县| 贡嘎县| 台北市| 邢台市| 白沙| 仙桃市| 偃师市| 铜山县| 黄骅市| 灵武市| 泸州市| 林西县| 梓潼县| 仪征市| 汶川县| 和顺县| 隆昌县| 寿阳县| 明光市| 邵阳县| 理塘县| 洮南市| 湘乡市| 洞头县| 巴彦淖尔市| 沁水县| 潮州市| 盐山县| 清远市| 新绛县| 北海市| 马公市| 溧水县| 北海市| 尼勒克县| 新营市| 北辰区| 岳普湖县| 临潭县| 凌源市| 锡林浩特市| 集贤县| 长治县| 扬州市| 平泉县| 察隅县| 襄城县| 萨嘎县| 微博| 沙河市| 玉环县| 大田县| 内江市| 金塔县| 崇文区| 永新县| 西峡县| 汤原县| 土默特左旗| 偏关县| 巴青县| 绥滨县| 伊春市| 贺兰县| 建湖县| 怀集县| 宾川县| 广西| 峨边| 吐鲁番市| 夏河县| 静乐县| 平定县| 保亭| 惠东县| 莱西市| 灌南县| 巫溪县| 休宁县| 延长县| 青冈县| 乌拉特后旗| 通江县| 武山县| 泰宁县| 德化县| 山东省| 来宾市| 西平县| 尚志市| 新建县| 沽源县| 太白县| 通许县| 平陆县| 商洛市| 苍梧县| 阿拉善右旗| 福海县| 罗山县| 长白| 娱乐| 林甸县| 扶绥县| 定西市| 四平市| 宜城市| 新蔡县| 海林市| 呼图壁县| 那曲县| 建阳市| 应用必备| 墨竹工卡县| 泸州市| 徐汇区| 天全县| 高碑店市| 抚远县| 石首市| 巴中市| 贺兰县| 清苑县| 正镶白旗| 肃北| 靖边县| 阳东县| 英德市| 繁昌县| 镇沅| 乐至县| 出国| 崇义县| 鹰潭市| 赣州市| 尖扎县| 长葛市| 历史| 固阳县| 九江县| 西充县| 彭水| 宁晋县| 四平市| 乌拉特中旗| 龙海市| 晋州市| 吴忠市| 崇左市| 竹山县| 河曲县| 荔浦县| 苗栗县| 鹤峰县| 巍山| 清徐县| 黄冈市| 九龙县| 元朗区| 文安县| 南京市| 洛阳市| 荥经县| 望城县| 富裕县| 伊吾县| 惠东县| 邯郸市| 黔江区| 寻甸| 宝坻区| 平江县| 博乐市| 仙居县| 彭山县| 江城| 托里县| 乌鲁木齐县| 凤阳县| 云霄县| 崇明县| 鸡西市| 商都县| 肃北| 伊川县| 金山区| 巍山| 卫辉市| 乌海市| 会理县| 登封市| 山阴县| 彭泽县| 福泉市| 德令哈市| 许昌市| 万山特区| 孟连| 泽库县| 铜川市| 布尔津县| 两当县| 镇康县| 盈江县| 高要市| 依安县| 桐乡市| 神木县| 平原县| 通州区| 平果县| 抚顺县| 资兴市| 房产| http://wap.dwcfwh.fit http://www.sucirk.fit http://wap.fggfow.fit http://dtxrjp.fit http://www.ptzein.fit http://www.qlnpuk.fit http://m.qgyxva.fit http://www.koerje.fit http://wap.bm1961lightz.fit http://wap.khowgx.fit http://onypnp.fit http://wap.oomssu.fit http://oeulua.fit http://wap.hftusr.fit http://coagsu.fit http://m.nzzcfn.fit http://wap.giablf.fit http://m.yokdlg.fit