[关闭]
@ysner 2018-10-16T00:17:09.000000Z 字数 1874 阅读 1881

[ZJOI2007]最大半连通子图

DP Tarjan 图论 拓扑排序


题面

latax题面真好看

解析

题目中概念挺抽象的。。。

说人话就是缩点后求最长链长度及方案数。

显然强联通分量缩成一点不会影响答案,并且缩完点后图为
要保证子图点可互达,只有一条链才可以。

然后就是缩点+拓扑排序+即可。

注意一下,如果缩点后建新图时连了重边,需要特判防止再次转移。

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