基环树一些有趣的事情
基环树，就是有一个环的树。有向基环树又分内向和外向基环树，当然也有无向的。
最近遇到的基环树真不少。有些题目赤裸裸的就告诉你，“给出一棵基环树（环套树）”，但是有的题会有一些标志。比如说n个点n条边（即n种关系），甚至有的题用更隐晦的手法来描写n个点n条边。那今天我就分享一些题目，尤其是后几道题目，非常有趣！
一、像HDU5915，CF835F，BZOJ1791，BZOJ2878这种明摆着是基环树的题，大家可以做一做，但这里不详细讲做法
（不是因为这些题简单，甚至这些题非常难，但有些无聊。）
二、BZOJ 3037 创世纪；
这是中文题，不解释题面。“每种世界元素都可以限制另外一种世界元素”，这句话暗示了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 }
三、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 }
四、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 }
那么本期分享也就结束了，各种表达或理解问题，欢迎各位提出或指正！
转载于:https://www.cnblogs.com/Alan-Luo/articles/9508282.html