[关闭]
@ysner 2018-08-17T21:50:08.000000Z 字数 2900 阅读 1895

[POI2012]FES-Festival

图论 tarjan 最短路


题面

有一个数列。现给定多组限制,限制分成类,第一类是,有个; 第二类是,有个。求这些数最多有多少种不同的取值。

解析

看到不等式就可以想到差分约束。

根据一些差分约束小常识,可以设表示最多能比大多少。
于是对第一类,。(双向边适用于定量比较)
第二类,由于是,。(单向边适用于定性比较)

一般来说,图中只要有非环就是不合法的。
观察一下建边,可以发现如果有正环,它的反边就会构成负环。
于是只要判负环就可以了。

如何判负环?
判负环(初始化一定要为正无穷)、判断都可以。
然而这题用前者会出现点小坑。
因为我们一般出发都会以为起点,而这一个图中不一定与负环联通。
怎么办?
找出联通块。虚构一个结点,与各个联通块建边权为的边(主要注意防止因该结点的建立而产生新的负环),然后从虚构点出发即可。

缩完点后,图中只剩边权为的边连接各联通块(第一类自己就能构成一个块)。由于“大于等于”这个关系不限制绝对大小,因而对答案没有影响(因可以无限扩大各联通块的值),可以忽略这些边。

于是各联通块内之和即为答案。
(话说只在联通块内跑的效率真是恐怖,判负环成了复杂度瓶颈)

完了?然而还要注意限制条件可以叠加,所以的赋值要取

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=605;
  17. struct Edge{int to,nxt,w;}e[N*400];
  18. int n,m1,m2,h[N],cnt,dis[N],dfn[N],low[N],tim,sta[N],top,scc,bl[N],sz[N],num[N],d[N][N];
  19. bool vis[N];
  20. ll ans;
  21. queue<int>Q;
  22. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  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)
  33. {
  34. dfn[u]=low[u]=++tim;vis[u]=1;sta[++top]=u;
  35. re int v;
  36. for(re int i=h[u];i+1;i=e[i].nxt)
  37. {
  38. re int v=e[i].to;
  39. if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
  40. else if(vis[v]) low[u]=min(low[u],dfn[v]);
  41. }
  42. if(dfn[u]==low[u])
  43. {
  44. ++scc;
  45. do{v=sta[top];bl[v]=scc;vis[v]=0;++sz[scc];top--;}while(u^v);
  46. }
  47. }
  48. il int fSPFA(re int st)
  49. {
  50. memset(dis,63,sizeof(dis));memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));
  51. while(!Q.empty()) Q.pop();
  52. dis[st]=0;num[st]=1;Q.push(st);vis[st]=1;
  53. while(!Q.empty())
  54. {
  55. re int u=Q.front();Q.pop();
  56. for(re int i=h[u];i+1;i=e[i].nxt)
  57. {
  58. re int v=e[i].to;
  59. if(dis[v]>dis[u]+e[i].w)
  60. {
  61. if((++num[v])>n) return 0;
  62. dis[v]=dis[u]+e[i].w;
  63. if(!vis[v]) vis[v]=1,Q.push(v);
  64. }
  65. }
  66. vis[u]=0;
  67. }
  68. return 1;
  69. }
  70. int main()
  71. {
  72. memset(h,-1,sizeof(h));memset(d,63,sizeof(d));
  73. re int u,v;
  74. n=gi();m1=gi();m2=gi();
  75. fp(i,1,m1) u=gi(),v=gi(),add(u,v,1),add(v,u,-1),d[u][v]=min(d[u][v],1),d[v][u]=min(d[v][u],-1);
  76. fp(i,1,m2) u=gi(),v=gi(),add(v,u,0),d[v][u]=min(d[v][u],0);
  77. fp(i,1,n) d[i][i]=min(d[i][i],0);
  78. fp(i,1,n) if(!dfn[i]) tarjan(i);
  79. memset(vis,0,sizeof(vis));
  80. fp(i,2,n)
  81. if(!vis[bl[i]])
  82. add(0,i,0),vis[bl[i]]=1;
  83. memset(vis,0,sizeof(vis));
  84. //if(!fSPFA(0)) {puts("NIE");return 0;}
  85. fp(o,1,scc)
  86. {
  87. re ll mx=0;
  88. fp(k,1,n)
  89. {
  90. if(bl[k]!=o) continue;
  91. fp(i,1,n)
  92. {
  93. if(bl[i]!=o||d[i][k]==d[0][0]) continue;
  94. fp(j,1,n)
  95. {
  96. if(bl[j]!=o||d[k][j]==d[0][0]) continue;
  97. d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  98. }
  99. }
  100. }
  101. fp(i,1,n)
  102. {
  103. if(bl[i]!=o) continue;
  104. fp(j,1,n)
  105. {
  106. if(bl[j]!=o) continue;
  107. mx=max(mx,d[i][j]);
  108. }
  109. }
  110. ans+=mx+1;
  111. }
  112. fp(i,1,n) if(d[i][i]<0) {puts("NIE");return 0;}
  113. printf("%lld\n",ans);
  114. return 0;
  115. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注