学习笔记--有向图的强连通分量

前言

是在不久前ZROI一场模拟赛中用了桥边来给有向图缩点结果WA掉,才发现有向图只能用强连通分量,太菜了

于是现在看集训一道题需要强连通分量缩点才开始填坑…

算法

《算法竞赛进阶指南》上讲得很清楚了,想学的我觉得看书就行了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void tarjan(int now){
int v;dfn[now]=low[now]=++tot;
st[++top]=now,vis[now]=1;//是否在栈中
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(vis[v])low[now]=min(low[now],low[v]);
}
if(dfn[now]==low[now]){
cnt++;
do{
v=st[top--];vis[v]=0;
scc[cnt].push_back(v);
in_scc[v]=cnt;
}while(v!=now);
}
return ;
}

例题

luogu2656采蘑菇

https://www.luogu.org/problemnew/show/P2656

分析

缩点后跑一遍最长路即可

但是写最长路我忽然发现一些有意思的问题

就是一开始写Dijsktra结果只有50分,最后对拍无果换了个SPFA就A了,当时就心态崩了

然后查错,发现了我对迪杰斯特拉求最长路之前的有些理解有些误解,也就是vis数组是不能使用的,为什么?

首先考虑这种情况

iYzF8P.png

如果我们求最短路,而且当前我们在$X$节点,那么设$A<B<C$,那么接下来肯定是堆中取出$Z$,再取出$Y$,这时候设置的vis,就阻止我们再次取出$Z$,为什么,因为我们是按照贪心的思想,找距离最短的点,我们第一次取出$Z$时就已经更新到了$Z$的最短路

但是考虑求最长路时,就算我们贪心地按照最长更新,如果设$B+C>A>B$,这时候我们第一次取出$Z$时$dis[z]=dis[x]+A$,但是我们可以在取出$Y$的时候更新$Z$,使得$dis[Z]=dis[X]+B+C$,这时候如果我们设置了vis数组,就无法再以这个新的更大值作为$dis[Z]$去更新其他点

代码(略微压行)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/*
Code By RyeCatcher
10.10
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
#include <utility>
#define ri register int
#define ll long long
#define ull unsigned long long
#define pb push_back
#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w".stdout);
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define SIZE 23333
using std::min;
using std::max;
using std::pair;
using std::queue;
using std::priority_queue;
using std::vector;
inline char gc(){
static char buf[SIZE],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while((c=getchar())>'9'||c<'0')ne=c=='-';x=c-48;
while((c=getchar())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=500005;
const int inf=0x7fffffff;
struct O_Edge{int ne,to,dis,val;}oe[maxn<<1];
int oh[maxn],oenum=1;
inline void oa_edge(int f,int to,int c,int v){oe[++oenum].ne=oh[f],oe[oenum].to=to,oe[oenum].dis=c,oe[oenum].val=v,oh[f]=oenum;}
struct S_Edge{int ne,to,dis;}se[maxn<<1];
int sh[maxn],senum=1;
inline void sa_edge(int f,int to,int c){se[++senum].ne=sh[f],se[senum].to=to,se[senum].dis=c,sh[f]=senum;}
ll w[maxn];
int n,m,in_scc[maxn],cnt=0;
int dfn[maxn],low[maxn],tot=0,st[maxn],top=0;
bool siv[maxn],vis[maxn];
void tarjan(int now){
int v;dfn[now]=low[now]=++tot,st[++top]=now,siv[now]=1;
for(ri i=oh[now];i;i=oe[i].ne){
v=oe[i].to;
if(!dfn[v]){tarjan(v);low[now]=min(low[now],low[v]);}
else if(siv[v])low[now]=min(low[now],low[v]);
}
if(dfn[now]==low[now]){
cnt++;
do{v=st[top--],siv[v]=0,in_scc[v]=cnt;}while(now!=v);
}
}
typedef pair<ll,int> pii;
int s;ll dis[maxn],ans=0;
void dij(){
int u,v;priority_queue <pair<ll,int> >q;
dis[s]=w[s],q.push(pii(-dis[s],s));
while(q.size()){
u=q.top().second;q.pop();
if(vis[u])continue;vis[u]=1;
for(ri i=sh[u];i;i=se[i].ne){
v=se[i].to;
//printf("%d %lld %d %lld %d\n",u,dis[u],v,dis[v],se[i].dis);
if(dis[v]<dis[u]+se[i].dis){dis[v]=dis[u]+se[i].dis,q.push(pii(-dis[v],v));}
}
}
return ;
}
int main(){
int x,y,z,zz,num;double p;
read(n),read(m);
for(ri i=1;i<=m;i++){
read(x),read(y),read(z);scanf("%lf",&p);zz=z,num=0;
while(zz){num+=zz,zz*=p;}
oa_edge(x,y,z,num);
}
for(ri i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(ri i=1;i<=n;i++){x=in_scc[i];
for(ri j=oh[i];j;j=oe[j].ne){
y=in_scc[oe[j].to];
if(x==y)w[x]+=oe[j].val;
}
}
for(ri i=1;i<=n;i++){x=in_scc[i];
for(ri j=oh[i];j;j=oe[j].ne){
y=in_scc[oe[j].to];
//printf("%d %d %d %d\n",i,y,x,in_scc[y]);
if(y!=x){sa_edge(x,y,w[y]+oe[j].dis);}//printf("%d %d %d %d %lld\n",i,in_scc[i],y,in_scc[y],w[y]);}
}
}
//for(ri i=1;i<=n;i++)printf("%d %d %lld\n",i,in_scc[i],w[in_scc[i]]);
read(s);s=in_scc[s];dij();
for(ri i=1;i<=cnt;i++)ans=max(ans,dis[i]);
printf("%lld\n",ans);
return 0;
}

CF894E

https://www.luogu.org/problemnew/show/CF894E

分析

双倍经验,上一题的加强版,但是算一个强连通分量中的一条边的最终贡献实际上就是找到最大的K $1+2+3+…+k<=dist$,然后$dist \times k - \sum _ {i=1}^K \sum_{j=1}^i j$,然后后面那个玩意大佬们都用数学公式推,我太菜只会用前缀和….

代码(注释略多)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/*
Code By RyeCatcher
10.10
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
#include <cmath>
#include <utility>
#define ri register int
#define ll long long
#define Ld long double
#define ull unsigned long long
#define pb push_back
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define SIZE 23333
using std::min;
using std::max;
using std::pair;
using std::sqrt;
using std::queue;
using std::priority_queue;
using std::vector;
inline char gc(){
static char buf[SIZE],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while((c=getchar())>'9'||c<'0')ne=c=='-';x=c-48;
while((c=getchar())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=1000005;
const int inf=0x7fffffff;
typedef pair<ll,int> pii;
int n,m;
struct Edge{
int ne,to,dis;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to,int c){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
edge[num_edge].dis=c;
h[f]=num_edge;
}
int cnt=0;
vector <int> scc[maxn];
vector <int> e_id[maxn];
ll w[maxn];//weight of scc
vector<pair<ll,int> >g[maxn];
int dfn[maxn],low[maxn],tot=0,in_scc[maxn];
int st[maxn],top=0;
bool vis[maxn];
void tarjan(int now){
int v;dfn[now]=low[now]=++tot;
st[++top]=now,vis[now]=1;
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
if(!dfn[v]){
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(vis[v])low[now]=min(low[now],low[v]);
}
if(dfn[now]==low[now]){
cnt++;
do{
v=st[top--];vis[v]=0;
scc[cnt].pb(v);
in_scc[v]=cnt;
//printf("(%d) %d\n",v,cnt);
}while(v!=now);
}
return ;
}
void dfs_1(int now){
int x=in_scc[now],v;vis[now]=1;
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;
//if(vis[v])continue;
if(x==in_scc[v]){
//mx_w[x]=max(mx_w[x],edge[i].dis);
e_id[x].pb(i);
}
if(!vis[v])dfs_1(v);
}
return ;
}
int deg[maxn];
void dfs_2(int now){
int x=in_scc[now],y,v;vis[now]=1;
for(ri i=h[now];i;i=edge[i].ne){
v=edge[i].to;y=in_scc[v];
//printf("%d %d %d %d\n",x,y,now,vis[v]);
if(x==y)continue;
deg[y]++;
g[x].pb(pii(w[y]+edge[i].dis,y));//add_edge(x,y,w[y]);
if(!vis[v])dfs_2(v);
}
return ;
}
int rt,arr[maxn];
ll dis[maxn],ans=0;
void dfs_3(int now){
int v;vis[now]=1;
for(ri i=0;i<g[now].size();i++){
v=g[now][i].second;
if(vis[v])continue;
dfs_3(v);
}
}
void spfa(){
queue <int> q;
int x,v;
for(ri i=1;i<=cnt;i++)dis[i]=-1e17,vis[i]=0;
vis[rt]=1,dis[rt]=w[rt];
q.push(rt);
while(q.size()){
x=q.front();q.pop();
for(ri i=0;i<g[x].size();i++){
v=g[x][i].second;
if(dis[v]<dis[x]+g[x][i].first){
dis[v]=dis[x]+g[x][i].first;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
vis[x]=0;
}
for(ri i=1;i<=cnt;i++)ans=max(ans,dis[i]);
return ;
}
ll pp[100005],psum[100005];
int main(){
for(ri i=1;i<=100003;i++){
pp[i]=pp[i-1]+i;
psum[i]=psum[i-1]+pp[i];
}
int x,y,z;
read(n),read(m);
for(ri i=1;i<=m;i++){
read(x),read(y),read(z);
add_edge(x,y,z);
}
for(ri i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(ri i=1;i<=n;i++)if(!vis[i])dfs_1(i);
ll p,k,sum=0;
for(ri i=1;i<=cnt;i++){
sum=0;
//printf("-%d-\n",e_id[i].size());
for(ri j=0;j<e_id[i].size();j++){
p=edge[e_id[i][j]].dis;
//printf("%lld\n",p);
k=(ll)(sqrt((double)p*2+0.25)-0.5);
//printf("%lld %lld %lld\n",p,k,psum[k]);
sum+=p*(k+1)-psum[k];
}
w[i]=sum;
//printf("--%lld--\n",sum);
}
memset(vis,0,sizeof(vis));
for(ri i=1;i<=n;i++)if(!vis[i])dfs_2(i);
//for(ri i=1;i<=n;i++)printf("%d %d %d\n",i,in_scc[i],deg[in_scc[i]]);
read(rt);
rt=in_scc[rt];
memset(vis,0,sizeof(bool)*(cnt+3));
spfa();
//for(ri i=1;i<=cnt;i++)if(!deg[i])rt=i;
printf("%lld\n",ans);
return 0;
}