<thead id="rfb9x"></thead>
    <address id="rfb9x"><dfn id="rfb9x"></dfn></address>

    <thead id="rfb9x"><var id="rfb9x"><output id="rfb9x"></output></var></thead>
    <address id="rfb9x"><dfn id="rfb9x"></dfn></address>

      <sub id="rfb9x"><dfn id="rfb9x"><ins id="rfb9x"></ins></dfn></sub>

      <address id="rfb9x"><dfn id="rfb9x"></dfn></address>
      <sub id="rfb9x"></sub><address id="rfb9x"><listing id="rfb9x"></listing></address>

      <sub id="rfb9x"><var id="rfb9x"><output id="rfb9x"></output></var></sub>
      <sub id="rfb9x"><var id="rfb9x"></var></sub>

      <address id="rfb9x"><dfn id="rfb9x"></dfn></address>

        <form id="rfb9x"></form>
        <address id="rfb9x"><var id="rfb9x"></var></address>

        <address id="rfb9x"></address>

        <sub id="rfb9x"><dfn id="rfb9x"><output id="rfb9x"></output></dfn></sub>

        <address id="rfb9x"><var id="rfb9x"></var></address>

          <sub id="rfb9x"></sub>

          基环树略解

          基环树

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

          总结

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

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

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

          相关文章
          相关标签/搜索
          香港tm46开奖结果3084今晚,六合彩开奖结果,493333王中王免费中特,2020最快开奖历史记录,本港台开奖现场直播今天开奖结果