4784: [Zjoi2017] 仙人掌
- Time Limit: 10 Sec Memory Limit: 512 MB
- Submit: 312 Solved: 181
- [Submit][Status][Discuss]
- Description
如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环, 我们就称之为仙人掌所谓简单环即不经过
重复的结点的环
现在九条可怜手上有一张无自环无重边的无向连通图, 但是她觉得这张图中的边数太少了, 所以她想要在图上连上
一些新的边同时为了方便的存储这张无向图, 图中的边数又不能太多经过权衡, 她想要加边后得到的图为一棵
仙人掌不难发现合法的加边方案有很多, 可怜想要知道总共有多少不同的加边方案两个加边方案是不同的当且
仅当一个方案中存在一条另一个方案中没有的边
Input
多组数据, 第一行输入一个整数 T 表示数据组数
每组数据第一行输入两个整数 n,m, 表示图中的点数与边数
接下来 m 行, 每行两个整数 u,v(1u,vn,u!=v) 表示图中的一条边保证输入的图
联通且没有自环与重边
- Sigma(n)<=5*10^5,m<=10^6,1<=m<=n*(n-1)/2
- Output
对于每组数据, 输出一个整数表示方案数, 当然方案数可能很大, 请对 998244353 取模后
输出
- Sample Input
- 2
- 3 2
- 1 2
- 1 3
- 5 4
- 1 2
- 2 3
- 2 4
- 1 5
- Sample Output
- 2
- 8
对于第一组样例合法加边的方案有 {}, {(2,3)}, 共 2 种
HINT
Source
ZJOI2017 DAY1 的题目质量相当高啊, 都是比较自然清新的思路加上非毒瘤的代码, 做起来真是一种享受
由于以前没有接触过仙人掌 DP, 所以这里要有一个清楚的认识
首先我们知道环套树 DP, 就是基环外向树类型的题目, 大致就是先找到基环, 然后对每棵树 DP, 最后枚举将环上的每一条边断开, 具体见 BZOJ1040 骑士
现在我们来看仙人掌图仙人掌图的定义是每条边最多在一个简单环中, 仔细分析可知, 实际上就是环和树的拼接, 如果将所有环拿走的话会发现, 整幅图会变成一个森林
那么我们就可以从这个方向考虑这个问题了第一个问题是, 如何判断一个图是不是仙人掌图首先建出 DFS 树, 然后对于每条反祖边, 将整个环上的边标记, 如果有边被标记超过两次则说明不是仙人掌图具体可以看下面的代码, 这里还有一种方法: 用树上差分实现标记
- void _dfs(int x,int f) {
- vi[x]=1;
- dep[x]=dep[f]+1;
- RAL(i,x) if(e[i].to!=f) {
- if(!vi[e[i].to]) _dfs(e[i].to,x);
- else if(dep[e[i].to]<dep[x]) {
- bt[x]++;bt[e[i].to]--;
- }
- }
- }
- int fl;
- void _gatherS(int x) {
- RAL(i,x) if(dep[x]+1==dep[e[i].to]) {
- _gatherS(e[i].to);bt[x]+=bt[e[i].to];
- if(!bt[e[i].to]) bi[i]=bi[i^1]=1;
- } if(bt[x]>1) fl=0;
- }
现在考虑如何 DP, 首先我们知道我们不可能在环上加边, 所以我们忽略掉环边, 这题就成功转化为了树形 DP 然后对于每棵树求出可以加边的方案数, 这个就是常规的 DP 具体可以看:
https://www.cnblogs.com/wfj2048/p/6636028.html
这样, 问题就轻松解决了思路非常清晰而巧妙, 确实是一道好题
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #define rep(i,l,r) for (int i=l; i<=r; i++)
- #define For(i,x) for (int i=h[x],k; i; i=nxt[i])
- typedef long long ll;
- using namespace std;
- const int N=500100,md=998244353;
- struct D{ int id,d; }a[N];
- int h[N],fa[N],dfn[N],lu[N],dep[N],to[N<<2],nxt[N<<2],n,m,u,v,cnt,T,nd;
- ll f[N],g[N],ans;
- bool cmp(const D &a,const D &b){ return a.d<b.d; }
- void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }
- void dfs(int x,int p){
- fa[x]=p; dfn[x]=++nd; dep[x]=dep[p]+1;
- For(i,x) if (!dfn[k=to[i]]) dfs(k,x);
- }
- void dp(int x,int rt){
- lu[x]=-1; f[x]=1; int tot=0;
- For(i,x) if ((k=to[i])!=fa[x] && lu[k]==1) tot++,dp(k,0),f[x]=f[x]*f[k]%md;
- if (!rt) f[x]=f[x]*g[tot+1]%md; else f[x]=f[x]*g[tot]%md;
- }
- void work(){
- scanf("%d%d",&n,&m); cnt=1;
- rep(i,1,n) lu[i]=fa[i]=dep[i]=dfn[i]=h[i]=0;
- rep(i,1,m) scanf("%d%d",&u,&v),add(u,v),add(v,u);
- nd=0; dfs(1,0);
- rep(i,1,m){
- int u=to[i<<1],v=to[(i<<1)|1];
- if (dfn[u]<dfn[v]) swap(u,v);
- while (u!=v){
- if (lu[u]==2){ printf("0\n"); return; }
- lu[u]++; u=fa[u];
- }
- }
- rep(i,1,n) a[i].id=i,a[i].d=dep[i];
- sort(a+1,a+n+1,cmp); ans=1;
- rep(i,1,n){
- int x=a[i].id; if (lu[x]==-1) continue;
- dp(x,1); ans=ans*f[x]%md;
- }
- printf("%lld\n",ans);
- }
- int main(){
- g[0]=g[1]=1; rep(i,2,500000) g[i]=(g[i-1]+(i-1)*g[i-2])%md;
- for (scanf("%d",&T); T--; ) work();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2522832.html