[关闭]
@ysner 2018-11-01T12:15:12.000000Z 字数 2421 阅读 1978

[noip模拟赛]小U的女装

图论 Tarjan 缩点 DP


题面

有一张边的、不一定联通的无向图。
如果选了一条边,就不能选其两个端点。
现在同时选点和边,那么最多能够选的点边数量和为多少。
同时,回答使点边数最大的方案数。

解析

设答案为,方案数为
讨论一下联通块的形态:

树的部分的
表示统计到号点,选不选该点的方案数。
然后从儿子转移,讨论一下就行。

综上,其实把强联通分量缩点后直接树形就行了。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  11. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  12. using namespace std;
  13. const int N=5e5+100,mod=998244353;
  14. int n,m,h[N],cnt=1,ans,dfn[N],low[N],sta[N],top,tot,sz[N],bl[N],scc,Esz[N],f[2][N],g[2][N];
  15. bool vis[N];
  16. struct dat{int u,v;}a[N<<1];
  17. struct Edge{int to,nxt;}e[N<<1];
  18. il void add(re int u,re int v)
  19. {
  20. e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
  21. e[++cnt]=(Edge){u,h[v]};h[v]=cnt;
  22. }
  23. il ll gi()
  24. {
  25. re ll x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void Tarjan(re int u,re int las)
  33. {
  34. dfn[u]=low[u]=++tot;sta[++top]=u;vis[u]=1;
  35. re int v;
  36. for(re int i=h[u];i+1;i=e[i].nxt)
  37. if((i^1)^las)
  38. {
  39. re int v=e[i].to;
  40. if(!dfn[v]) Tarjan(v,i),low[u]=min(low[u],low[v]);
  41. else if(vis[v]) low[u]=min(low[u],dfn[v]);
  42. }
  43. if(dfn[u]==low[u])
  44. {
  45. ++scc;
  46. do{v=sta[top--];vis[v]=0;++sz[scc];bl[v]=scc;}while(u^v);
  47. }
  48. }
  49. il void dfs(re int u)
  50. {
  51. f[0][u]=sz[u];f[1][u]=Esz[u];g[0][u]=g[1][u]=1;vis[u]=1;
  52. for(re int i=h[u];i+1;i=e[i].nxt)
  53. {
  54. re int v=e[i].to;
  55. if(vis[v]) continue;
  56. dfs(v);
  57. if(f[0][v]>f[1][v]) f[0][u]+=f[0][v],g[0][u]=1ll*g[0][u]*g[0][v]%mod;
  58. if(f[0][v]==f[1][v]) f[0][u]+=f[0][v],g[0][u]=1ll*g[0][u]*(g[0][v]+g[1][v])%mod;
  59. if(f[0][v]<f[1][v]) f[0][u]+=f[1][v],g[0][u]=1ll*g[0][u]*g[1][v]%mod;
  60. if(f[0][v]>f[1][v]+1) f[1][u]+=f[0][v],g[1][u]=1ll*g[1][u]*g[0][v]%mod;
  61. if(f[0][v]==f[1][v]+1) f[1][u]+=f[0][v],g[1][u]=1ll*g[1][u]*(g[0][v]+g[1][v])%mod;
  62. if(f[0][v]<f[1][v]+1) f[1][u]+=f[1][v]+1,g[1][u]=1ll*g[1][u]*g[1][v]%mod;
  63. }
  64. }
  65. int main()
  66. {
  67. memset(h,-1,sizeof(h));
  68. n=gi();m=gi();
  69. fp(i,1,m) a[i].u=gi(),a[i].v=gi(),add(a[i].u,a[i].v);
  70. fp(i,1,n) if(!dfn[i]) Tarjan(i,0);
  71. memset(h,-1,sizeof(h));cnt=0;
  72. fp(i,1,m)
  73. {
  74. re int u=a[i].u,v=a[i].v;
  75. if(bl[u]^bl[v]) add(bl[u],bl[v]);
  76. else ++Esz[bl[u]];
  77. }
  78. n=scc;tot=1;
  79. fp(i,1,n)
  80. if(!vis[i])
  81. {
  82. dfs(i);
  83. if(f[0][i]<f[1][i]) ans+=f[1][i],tot=1ll*tot*g[1][i]%mod;
  84. if(f[0][i]==f[1][i]) ans+=f[1][i],tot=1ll*tot*(g[0][i]+g[1][i])%mod;
  85. if(f[0][i]>f[1][i]) ans+=f[0][i],tot=1ll*tot*g[0][i]%mod;
  86. }
  87. printf("%d\n%d\n",ans,tot);
  88. return 0;
  89. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注