基環樹，就是有一個環的樹。有向基環樹又分內向和外向基環樹，當然也有無向的。

　　最近遇到的基環樹真不少。有些題目赤裸裸的就告訴你，“給出一棵基環樹（環套樹）”，但是有的題會有一些標志。比如說n個點n條邊（即n種關系），甚至有的題用更隱晦的手法來描寫n個點n條邊。那今天我就分享一些題目，尤其是后幾道題目，非常有趣！

一、像HDU5915，CF835F，BZOJ1791，BZOJ2878這種明擺著是基環樹的題，大家可以做一做，但這里不詳細講做法

　　（不是因為這些題簡單，甚至這些題非常難，但有些無聊。）

二、BZOJ 3037 創世紀；

　　這是中文題，不解釋題面?！懊糠N世界元素都可以限制另外一種世界元素”，這句話暗示了n個點，n條邊，于是把a限制b當成a向b連一條有向邊。于是很顯然，一個點可以被使用的前提是有一個未被使用的前驅，所以可以dp，但是貪心算法也是可以的，貪心策略是一開始將每個入度為零的點加入隊列，然后順次按要求選擇；最后把環拎出來，環長/2加到答案里，這道題就結束了；正確性可以自行證明，或看這里；

有代碼 ?

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 const int MAXN=1000005; 9 int n,in[MAXN],a[MAXN],ans=0; 10 bool vis[MAXN];queue<int>q; 11 int main(){ 12 scanf("%d",&n); 13 for(int i=1;i<=n;i++) 14 scanf("%d",&a[i]),in[a[i]]++; 15 for(int i=1;i<=n;i++) 16 if(!in[i]) q.push(i); 17 while(q.size()){ 18 if(!vis[a[q.front()]]&&!vis[q.front()]){ 19 vis[a[q.front()]]=1;ans++; 20 if(--in[a[a[q.front()]]]==0) 21 q.push(a[a[q.front()]]); 22 } vis[q.front()]=1;q.pop(); 23 } 24 for(int i=1;i<=n;i++) 25 if(!vis[i]){ 26 int cnt=1,t=i; 27 while(a[t]!=i) cnt++,vis[t]=1,t=a[t]; 28 vis[t]=1;ans+=cnt>>1; 29 } printf("%d\n",ans);return 0; 30 } greedy

?

?

三、BZOJ1040 騎士 ；

　　這道題也是一樣，限制了每個人有一個仇敵。就是環套樹的關系。仔細觀察題目我們會發現，任何兩個有邊的點都不能被同時選入騎士團中，所以這是一顆無向基環樹。我們可以用樹形dp來做，從某一條在環上的邊斷環成鏈，然后樹中就沒有環了，可以直接進行樹形dp，這樣，可以從被我們斷掉的那條邊連接的兩點入手，先強制不選某一個，做一遍樹上dp，再強制不選另一個，再做一遍，兩遍最優解取max就是最終答案！為什么這樣能體現所有的情況呢？各位可以思考一下。

也有代碼

?

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 const int MAXN=1000005; 8 struct node{ 9 int y,nxt; 10 }edge[MAXN*2];int indx=0; 11 int ra[MAXN],rb[MAXN]; 12 int fa[MAXN],head[MAXN],n,m=0; 13 ll f[MAXN],g[MAXN],v[MAXN],ans,t=0; 14 int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);} 15 ll max(ll a,ll b){return a>b?a:b;} 16 void add(int x,int y){ 17 edge[++indx].nxt=head[x]; 18 edge[indx].y=y;head[x]=indx; 19 } 20 void dfs(int x,int pre){ 21 f[x]=v[x],g[x]=0; 22 for(int i=head[x],y;~i;i=edge[i].nxt){ 23 if((y=edge[i].y)==pre) continue; 24 dfs(y,x);g[x]+=max(f[y],g[y]); 25 f[x]+=g[y]; 26 } 27 } 28 int main(){ 29 scanf("%d",&n); 30 for(int i=1;i<=n;i++) fa[i]=i; 31 memset(head,-1,sizeof(head)); 32 for(int i=1,y;i<=n;i++){ 33 scanf("%lld%d",&v[i],&y); 34 if(get(i)!=get(y)){ 35 add(i,y);add(y,i); 36 fa[fa[i]]=fa[y]; 37 } else ra[++m]=i,rb[m]=y; 38 } 39 for(int i=1;i<=m;i++){ 40 dfs(ra[i],0);t=g[ra[i]]; 41 dfs(rb[i],0);t=max(t,g[rb[i]]); 42 ans+=t; 43 } printf("%lld\n",ans);return 0; 44 } dp

?

?

?

四、RQN PID730混合藥品

　　又是一道兩兩不能放在一起的模型，現在我們對于這樣的模型應該已經非常熟悉了。對于這道題，我們需要分成環部分和樹部分進行考慮，首先明確我們要在一棵基環樹上進行k染色，然后有邊的兩個點顏色不同，對于環來說，我們要dp求出染色方案，對于樹來說，滿足要求的方案數可以用組合數學來解，公式是(k-1)^siz，siz代表樹的大小（不包括在環上的那個點）。最后用乘法原理把方案數相乘作為最終答案！

更有代碼

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #define ms(a,x) memset(a,x,sizeof(a)) 7 using namespace std; 8 const int MAXN=105; 9 const int mod=1e9+7; 10 long long n,m,k,t,tot,ans,p,num;bool vis[MAXN]; 11 long long c[MAXN],f[MAXN],fa[MAXN];bool bz[MAXN]; 12 int main(){ 13 scanf("%lld",&t); 14 while(t--){ 15 scanf("%lld%lld",&n,&k);num=n;ms(vis,0); 16 for(int i=0;i<n;i++) scanf("%lld",&fa[i]); 17 f[1]=k;f[2]=k*(k-1)%mod;f[3]=f[2]*(k-2)%mod;ans=1; 18 for(int i=4;i<=n;i++) f[i]=((f[i-1]*(k-2)%mod)+(f[i-2]*(k-1)%mod))%mod; 19 for(int i=0;i<n;i++) 20 if(!vis[i]){ 21 for(p=i,tot=0,ms(bz,0);!bz[p];bz[p]=1,p=fa[p],tot++); 22 if(p^i) continue; 23 for(p=i,ms(bz,0);!bz[p];bz[p]=vis[p]=1,p=fa[p]); 24 num-=tot;ans=(1LL*ans*f[tot])%mod; 25 } 26 for(int i=1;i<=num;i++){ 27 ans=ans*(k-1)%mod; 28 } printf("%lld\n",ans); 29 } return 0; 30 } 乘法原理

?

?

五、前面我們見到了求最優解的題，也有求方案數的題，下面我們看一道既要求出最優解，也要求出方案數的題；

　　HDU6403：題意：給定 n 張卡片，每張卡片正反面各有一個數。問至少要翻轉多少張卡片，才能使正面向上的數互
不相同，并求方案數。

　　啊，這個題就confusing了，這看似二分圖又做不了，看似基環樹又無法建圖的題，可怎么辦啊。。。

　　不要著急，我們仔細地挖掘一下題目中的信息，每張卡片連接了兩個數，這是不是就像一個邊連接兩個點的關系？于是我們就有思路了，但在處理關系的時候我們要稍微動一下腦筋。我們從當前每張卡的背面的數向正面的數連一條有向邊，這樣，所有有入度的點就是朝上的數字，我們要求朝上的數字各不相同，是不是就可以抽象成“使任意點的入度小于等于一，最少需要翻轉幾條邊！”，那這個題的模型我們就知道了，是建雙向邊，用0/1區分方向的題。我們首先把環上的方向確定，然后在樹上我們統計每個點作為根時各邊的最小翻轉次數，然后最終將方案數合并。（處理過于麻煩，本蒻選擇直接抄題解。。。）

還有代碼

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=200005; 8 const int mod=998244353; 9 struct node{ 10 int y,z,nxt; 11 }edge[MAXN];int indx=0,s=-1,t=-1; 12 int mn,ways,ans=0,tway; 13 int head[MAXN],n,m,k,cnt=0,num=0,sign=-1; 14 bool vis[MAXN],flag;int f[MAXN],g[MAXN]; 15 char readchar(){ 16 static char buf[100000], *l=buf,*r=buf; 17 if(l==r) r=(l=buf)+fread(buf,1,100000,stdin); 18 if(l==r) return EOF; 19 return *l++; 20 } 21 inline int read(){ 22 int x=0,f=1;char ch=readchar(); 23 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=readchar();} 24 while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=readchar();} 25 return x*f; 26 } 27 void add(int x,int y,int z){ 28 edge[++indx].y=y;edge[indx].z=z; 29 edge[indx].nxt=head[x];head[x]=indx; 30 } int st[MAXN],tp=0; 31 void check(int x){ 32 num++;vis[x]=1; 33 for(int i=head[x],y;i;i=edge[i].nxt){ 34 cnt++;if(!vis[y=edge[i].y]) check(y); 35 } return ; 36 } 37 void dfs(int x,int fa){ 38 vis[x]=1;f[x]=0; 39 for(int i=head[x],y;i;i=edge[i].nxt) 40 if(!vis[y=edge[i].y]){ 41 dfs(y,x);f[x]+=f[y]+(!edge[i].z); 42 } else if(y!=fa) s=x,t=y,sign=i; 43 } 44 void solve(int x,int fa){ 45 st[tp++]=x;mn=min(mn,g[x]); 46 for(int i=head[x],y;i;i=edge[i].nxt) 47 if(i!=fa&&(i^1)!=fa&&i!=sign&&i!=(sign^1)){ 48 g[y=edge[i].y]=g[x]+(edge[i].z?1:-1); 49 solve(y,i); 50 }return ; 51 } 52 int main(){ 53 int ca=read(); 54 while(ca--){ 55 indx=ways=1;flag=0;ans=0; 56 memset(head,0,sizeof(head)); 57 memset(vis,0,sizeof(vis)); 58 n=read(); 59 for(int i=1,x,y;i<=n;i++){ 60 x=read(),y=read(); 61 add(y,x,1);add(x,y,0); 62 } 63 for(int i=1;i<=2*n;i++) 64 if(!vis[i]){ 65 num=cnt=0;check(i); 66 if(cnt/2>num){flag=1;break;} 67 } if(flag){puts("-1 -1");continue;} 68 memset(vis,0,sizeof(vis)); 69 for(int i=1;i<=2*n;i++) 70 if(!vis[i]){ 71 s=t=sign=-1;dfs(i,0); 72 mn=0x3fffffff;tway=tp=0;g[i]=f[i]; 73 solve(i,0);if(s==-1){ 74 for(int j=0;j<tp;j++) 75 if(g[st[j]]==mn) tway++; 76 } else 77 mn=min(g[s]+edge[sign].z,g[t]+(!edge[sign].z)), 78 tway=(g[s]+edge[sign].z==g[t]+(!edge[sign].z)?2:1); 79 ans+=mn;ways=1LL*ways*tway%mod; 80 } printf("%d %d\n",ans,ways); 81 } return 0; 82 } dfs

?

那么本期分享也就結束了，各種表達或理解問題，歡迎各位提出或指正！

?

轉載于:https://www.cnblogs.com/Alan-Luo/articles/9508282.html

總結

以上是生活随笔為你收集整理的基环树一些有趣的事情的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。