网站seo在线诊断,wordpress 自动上传插件,网站如何做进一步优化,网站建设亇金手指专业$Tarjan$缩点 Tarjan的第二个应用就是求缩点啦。缩点虽然比割点麻烦一点#xff0c;但是用处也比割点要大不少。 本来要学另外两个缩点算法的,但是似乎没什么用...$MST$里确实有只能有$prim$或者只能用$kruscal$的题目#xff0c;但是这三种缩点...在网上没有找到介绍它们之间… $Tarjan$缩点 Tarjan的第二个应用就是求缩点啦。缩点虽然比割点麻烦一点但是用处也比割点要大不少。 本来要学另外两个缩点算法的,但是似乎没什么用...$MST$里确实有只能有$prim$或者只能用$kruscal$的题目但是这三种缩点...在网上没有找到介绍它们之间作用差异的文章,可能真的没有什么区别吧. 缩点是对于有向图来说的。首先什么是强连通分量里面的点两两之间互相可达。如果一道题中互相可达的点有某种神秘的联系(一个强连通分量等价于一个点的作用)时就可以进行缩点。那么缩点有什么好处呢显而易见的是可以快把一些等价的点的操作一起做了还有一个就是缩完点之后的图必然是一个$Dag$可以在上面跑一些拓扑排序啊$dp$啊之类的东西。 首先先看一个模板吧 缩点https://www.luogu.org/problemnew/show/P3387 题意概述缩点后跑dp求点权最大的路径每个点的点权只算一次 1 # include cstdio2 # include iostream3 # define R register int4 5 using namespace std;6 7 int H,k,bp,cnt,h,Top0,n,m,x,y,a[10009],firs[10009],Firs[10009],sta[10009];8 int id[10009],low[10009],vis[10009],A[10009];9 int dp[10009],color[10009],r[10009],q[100009];10 struct edge11 {12 int too,nex;13 }g[100009],G[100009];14 15 void add1(int x,int y)16 {17 g[h].tooy;18 g[h].nexfirs[x];19 firs[x]h;20 }21 22 void add2(int x,int y)23 {24 G[H].tooy;25 G[H].nexFirs[x];26 Firs[x]H;27 }28 29 void dfs(int x)30 {31 low[x]id[x]cnt;32 vis[x]1;33 sta[Top]x;34 int j;35 for (R ifirs[x];i;ig[i].nex)36 {37 jg[i].too;38 if(!id[j])39 {40 dfs(j);41 low[x]min(low[x],low[j]);42 }43 else44 {45 if(vis[j]) low[x]min(low[x],low[j]);46 }47 }48 if(id[x]low[x])49 {50 bp;51 color[x]bp;52 A[bp]a[x];53 vis[x]0;54 while (sta[Top]!x)55 {56 color[ sta[Top] ]bp;57 A[bp]a[ sta[Top] ];58 vis[ sta[Top] ]0;59 Top--;60 }61 Top--;62 }63 }64 65 int main()66 {67 scanf(%d%d,n,m);68 for (R i1;in;i)69 scanf(%d,a[i]);70 for (R i1;im;i)71 {72 scanf(%d%d,x,y);73 add1(x,y);74 }75 for (R i1;in;i)76 if(!id[i]) dfs(i);77 for (R i1;in;i)78 for (R jfirs[i];j;jg[j].nex)79 {80 kg[j].too;81 if(color[i]!color[k]) add2(color[i],color[k]),r[ color[k] ];82 }83 int num0;84 for (R i1;ibp;i)85 if(!r[i]) q[num]i,dp[i]A[i];86 for (R i1;inum;i)87 {88 for (R jFirs[ q[i] ];j;jG[j].nex)89 {90 kG[j].too;91 r[k]--;92 dp[k]max(dp[k],dp[ q[i] ]A[k]);93 if(!r[k]) q[num]k;94 }95 }96 int ansdp[1];97 for (R i2;ibp;i)98 ansmax(ans,dp[i]);99 coutans;
100 return 0;
101 } 缩点 牛的舞会https://www.luogu.org/problemnew/show/P2863 题意概述找到大小大于1的强连通分量个数。 板子题*2再开一个数组记录每个连通分量的大小就行啦。 1 # include cstdio2 # include iostream3 # define R register int4 5 using namespace std;6 7 const int maxn10009;8 int num0,x,y,h,n,m;9 int Ans0,ans[maxn],cnt0,Top0,color[maxn],sta[maxn],vis[maxn],id[maxn],low[maxn],firs[maxn];
10 struct edge
11 {
12 int too,nex;
13 }g[50009];
14
15 inline void add(int x,int y)
16 {
17 g[h].tooy;
18 g[h].nexfirs[x];
19 firs[x]h;
20 }
21
22 inline void dfs(int x)
23 {
24 id[x]low[x]cnt;
25 vis[x]true;
26 sta[Top]x;
27 int j;
28 for (R ifirs[x];i;ig[i].nex)
29 {
30 jg[i].too;
31 if(!id[j])
32 {
33 dfs(j);
34 low[x]min(low[x],low[j]);
35 }
36 else
37 {
38 if(vis[j])
39 low[x]min(low[x],low[j]);
40 }
41 }
42 if(id[x]low[x])
43 {
44 color[x]num;
45 vis[x]0;
46 while (sta[Top]!x)
47 {
48 color[ sta[Top] ]num;
49 vis[ sta[Top] ]0;
50 Top--;
51 }
52 Top--;
53 }
54 }
55
56 int main()
57 {
58 scanf(%d%d,n,m);
59 for (R i1;im;i)
60 {
61 scanf(%d%d,x,y);
62 add(x,y);
63 }
64 for (R i1;in;i)
65 if(!id[i]) dfs(i);
66 for (R i1;in;i)
67 ans[ color[i] ];
68 for (R i1;in;i)
69 if(ans[i]1) Ans;
70 coutAns;
71 return 0;
72 } 牛的舞会 受欢迎的牛https://www.luogu.org/problemnew/show/P2341 题意概述求图中某种点的个数其余所有的点都可以通过某些路径到达它这里的点。 因为路径可以绕来绕去所以一个强连通分量里的点要么全是这种点要么全都不是。如果一个强连通分量有出边它必然不是一个受欢迎的强连通分量它连出去的边一定没有连回来否则就合成同一个连通分量了。也就是说找到唯一一个出度为$0$的强连通分量它的大小就是答案。如果有不止一个这样的分量说明图不连通答案为$0$。 1 # include cstdio2 # include iostream3 # define R register int4 5 using namespace std;6 7 int n,m,h,x,y,firs[10009],a[10009];8 int id[10009],low[10009],vis[10009],sta[10009];9 int color[10009],cnt,bp,Top;
10 int c[10009];
11 struct edge
12 {
13 int too,nex;
14 }g[50009];
15
16 void add(int x,int y)
17 {
18 g[h].tooy;
19 g[h].nexfirs[x];
20 firs[x]h;
21 }
22
23 void dfs(int x)
24 {
25 id[x]low[x]cnt;
26 vis[x]true;
27 sta[Top]x;
28 int j;
29 for (R ifirs[x];i;ig[i].nex)
30 {
31 jg[i].too;
32 if(!id[j])
33 {
34 dfs(j);
35 low[x]min(low[x],low[j]);
36 }
37 else
38 {
39 if(vis[j])
40 low[x]min(low[x],low[j]);
41 }
42 }
43 if(low[x]id[x])
44 {
45 color[x]bp;
46 a[bp];
47 vis[x]0;
48 while (sta[Top]!x)
49 {
50 color[ sta[Top] ]bp;
51 a[bp];
52 vis[ sta[Top] ]0;
53 Top--;
54 }
55 Top--;
56 }
57 }
58
59 int main()
60 {
61 scanf(%d%d,n,m);
62 for (R i1;im;i)
63 {
64 scanf(%d%d,x,y);
65 add(x,y);
66 }
67 for (R i1;in;i)
68 if(!id[i]) dfs(i);
69 for (R i1;in;i)
70 for (R jfirs[i];j;jg[j].nex)
71 {
72 if(color[i]!color[ g[j].too ])
73 c[ color[ i ] ];
74 }
75 int ans0;
76 for (R i1;ibp;i)
77 {
78 if(c[i]0)
79 {
80 if(ans0) ansa[i];
81 else
82 {
83 printf(0);
84 return 0;
85 }
86 }
87 }
88 printf(%d,ans);
89 return 0;
90 } 受欢迎的牛 在农场万圣节https://www.luogu.org/problemnew/show/P2921 题意概述给定一张有向图求从每个点出发路过的点的个数。每个点的后继唯一不能走重复点。 看起来缩点非常可行且走进一个分量就出不来了所以缩点后进行记忆化搜索就可以啦。这道题有一个简化的地方每个点只有单一的后继所以不用前向星只用一个$nex$数组也是完全可以的。 1 # include cstdio2 # include iostream3 # define R register int4 5 using namespace std;6 7 const int maxn100009;8 int n,cnt,bp,Top;9 int nex[maxn],vis[maxn],A[maxn],dp[maxn];
10 int low[maxn],id[maxn],sta[maxn],color[maxn];
11 int Nex[maxn],touc[maxn];
12
13 void dfs(int x)
14 {
15 id[x]low[x]cnt;
16 vis[x]1;
17 sta[Top]x;
18 if(!id[ nex[x] ])
19 {
20 dfs(nex[x]);
21 low[x]min(low[x],low[ nex[x] ]);
22 }
23 else
24 {
25 if(vis[ nex[x] ]) low[x]min(low[x],low[ nex[x] ]);
26 }
27 if(low[x]id[x])
28 {
29 color[x]bp;
30 A[bp];
31 vis[x]0;
32 while (sta[Top]!x)
33 {
34 color[ sta[Top] ]bp;
35 vis[ sta[Top] ]0;;
36 A[bp];
37 Top--;
38 }
39 Top--;
40 }
41 }
42
43 int find_out(int x)
44 {
45 if(touc[x]) return dp[x];
46 if(Nex[x]0)
47 {
48 touc[x]true;
49 return dp[x];
50 }
51 dp[x]find_out(Nex[x]);
52 touc[x]true;
53 return dp[x];
54 }
55
56 int main()
57 {
58 scanf(%d,n);
59 for (R i1;in;i)
60 scanf(%d,nex[i]);
61 for (R i1;in;i)
62 if(!id[i]) dfs(i);
63 for (R i1;in;i)
64 {
65 if(color[i]!color[ nex[i] ])
66 Nex[ color[i] ]color[ nex[i] ];
67 dp[ color[i] ]A[ color[i] ];
68 }
69 for (R i1;in;i)
70 printf(%d\n,find_out(color[i]));
71 return 0;
72 } 在农场万圣节 最大半联通子图:https://www.luogu.org/problemnew/show/P2272 题意概述:图中极大半联通子图计数.半联通子图:对于每个无序点对$(u,v)$,满足其中一个点可以到达另一个点. 不难看出强连通分量里的点都是满足条件的,而且一条缩点后的链都是满足条件的,也就是最长链计数.注意重连边时可能会出现重边,排序,去重即可. 1 // luogu-judger-enable-o22 # include cstdio3 # include iostream4 # include cstring5 # include cmath6 # include algorithm7 # include string8 # include bitset9 # include queue10 # define R register int11 12 using namespace std;13 14 const int maxn100005;15 const int maxm1000006;16 int k,a,b,n,m,x,h,h2,firs[maxn],firs2[maxn],cnt;17 int r[maxn],id[maxn],low[maxn],color[maxn],siz[maxn],sta[maxn],bp,Top,vis[maxn];18 int dp[maxn],f[maxn],ans1,ans2;19 queue int q;20 bitset maxn t;21 struct edge22 {23 int too,nex;24 }g[maxm],g2[maxm];25 26 void dfs (int x)27 { 28 low[x]id[x]cnt;29 vis[x]true;30 sta[Top]x;31 int j;32 for (R ifirs[x];i;ig[i].nex)33 {34 jg[i].too;35 if(!id[j])36 dfs(j),low[x]min(low[x],low[j]);37 else38 if(vis[j]) low[x]min(low[x],low[j]);39 }40 if(low[x]id[x])41 {42 color[x]bp;43 siz[bp];44 vis[x]0;45 while (sta[Top]!x)46 {47 color[ sta[Top] ]bp;48 vis[ sta[Top] ]0;49 siz[bp];50 Top--;51 }52 Top--;53 }54 }55 56 void add1 (int x,int y)57 { 58 g[h].tooy;59 g[h].nexfirs[x];60 firs[x]h;61 }62 63 void add2 (int x,int y)64 {65 g2[h2].tooy;66 g2[h2].nexfirs2[x];67 firs2[x]h2;68 }69 70 inline char gc()71 {72 static char now[122],*S,*T;73 if (TS)74 {75 T(Snow)fread(now,1,122,stdin);76 if (TS) return EOF;77 }78 return *S;79 }80 inline int read()81 {82 R x0,f1;83 register char chgc();84 while(!isdigit(ch))85 {86 if (ch-) f-1;87 chgc();88 }89 while(isdigit(ch)) x(x1)(x3)ch-0,chgc();90 return x*f;91 }92 93 int main()94 {95 scanf(%d%d%d,n,m,x);96 for (R i1;im;i)97 {98 aread(),bread();99 add1(a,b);
100 }
101 for (R i1;in;i)
102 if(!id[i]) dfs(i);
103 for (R i1;in;i)
104 for (R jfirs[i];j;jg[j].nex)
105 {
106 kg[j].too;
107 if(color[i]color[k]) continue;
108 add2(color[i],color[k]);
109 }
110 for (R i1;ibp;i)
111 {
112 for (R jfirs2[i];j;jg2[j].nex)
113 {
114 kg2[j].too;
115 if(t[k]) g2[j].too0;
116 else r[k];
117 t[k]true;
118 }
119 for (R jfirs2[i];j;jg2[j].nex)
120 {
121 kg2[j].too;
122 t[k]false;
123 }
124 }
125 for (R i1;ibp;i)
126 if(!r[i]) q.push(i),dp[i]siz[i],f[i]1;
127 int beg,j;
128 while (q.size())
129 {
130 begq.front();
131 q.pop();
132 for (R ifirs2[beg];i;ig2[i].nex)
133 {
134 jg2[i].too;
135 if(dp[beg]siz[j]dp[j]) dp[j]dp[beg]siz[j],f[j]f[beg];
136 else if(dp[beg]siz[j]dp[j]) f[j](f[j]f[beg])%x;
137 r[j]--;
138 if(!r[j]) q.push(j);
139 }
140 }
141 for (R i1;ibp;i)
142 {
143 if(dp[i]ans1)
144 ans1dp[i],ans2f[i];
145 else if(dp[i]ans1)
146 ans2(ans2f[i])%x;
147 }
148 printf(%d\n%d,ans1,ans2);
149 return 0;
150 } 最大半联通子图 抢掠计划:https://www.luogu.org/problemnew/show/P3627 题意概述:缩点dp. 这道题的关键点:源点是给定的 注意最开始入队的时候和平常没有什么区别但是要单独维护一个$f$数组表示能否从源点到达这个地方. 1 # include cstdio2 # include iostream3 # include queue4 # define R register int5 6 using namespace std;7 8 const int maxn500005;9 int TO[maxn],n,m,x,y,s,p,cnt,bp,vis[maxn],v[maxn],id[maxn],low[maxn],col[maxn],A[maxn],ans,sta[maxn],r[maxn],dp[maxn],Top,goa[maxn];10 struct edge11 {12 int too,nex;13 };14 int q[maxn],h,t;15 namespace bef16 {17 int h0,firs[maxn]{0};18 edge g[maxn];19 void add (int x,int y)20 {21 g[h].nexfirs[x];22 firs[x]h;23 g[h].tooy;24 }25 }26 namespace aft27 {28 int h0, firs[maxn]{0};29 edge g[maxn];30 void add(int x, int y)31 {32 g[h].nexfirs[x];33 firs[x]h;34 g[h].tooy;35 }36 }37 38 void Tarjan (int x)39 {40 id[x]low[x]cnt;41 sta[Top]x;42 vis[x]1;43 int j;44 for (R ibef::firs[x];i;ibef::g[i].nex)45 {46 jbef::g[i].too;47 if(!id[j])48 {49 Tarjan(j);50 low[x]min(low[x],low[j]);51 }52 else53 {54 if(vis[j]) low[x]min(low[x],id[j]);55 }56 }57 if(low[x]id[x])58 {59 col[x]bp;60 A[bp]v[x];61 vis[x]0;62 while (sta[Top]!x)63 {64 A[bp]v[ sta[Top] ];65 col[ sta[Top] ]bp;66 vis[ sta[Top] ]0;67 Top--;68 }69 Top--;70 }71 }72 73 int main()74 {75 scanf(%d%d,n,m);76 for (R i1;im;i)77 {78 scanf(%d%d,x,y);79 bef::add(x,y);80 }81 for (R i1;in;i)82 scanf(%d,v[i]);83 scanf(%d%d,s,p);84 for (R i1;ip;i)85 scanf(%d,goa[i]);86 for (R i1;in;i)87 if(!id[i]) Tarjan(i);88 int beg,k;89 for (R i1;in;i)90 for (R jbef::firs[i];j;jbef::g[j].nex)91 {92 kbef::g[j].too;93 if(col[i]!col[k]) aft::add(col[i],col[k]),r[ col[k] ];94 95 }96 for (R i1;ibp;i)97 if(!r[i]) q[t]i;98 h1;99 dp[ col[s] ]A[ col[s] ];
100 TO[ col[s] ]1;
101 while (ht)
102 {
103 begq[h];
104 h;
105 for (R iaft::firs[beg];i;iaft::g[i].nex)
106 {
107 kaft::g[i].too;
108 r[k]--;
109 if(TO[beg])
110 {
111 TO[k]true;
112 dp[k]max(dp[k],dp[beg]A[k]);
113 }
114 if(!r[k]) q[t]k;
115 }
116 }
117 for (R i1;ip;i)
118 ansmax(ans,dp[ col[ goa[i] ] ]);
119 printf(%d,ans);
120 return 0;
121 } 抢掠计划 间谍网络:https://loj.ac/problem/10095 首先缩点,然后找到入度为$0$的点收买即可.对于一个强联通分量里的点,如果要收买只需要收买那个最便宜的即可. 1 # include cstdio2 # include iostream3 # include cstring4 # include queue5 # define R register int6 7 using namespace std;8 9 const int maxn3003;10 const int maxm8003;11 int n,p,x,y,v,m,h,cnt,beg,ans;12 int a[maxn],id[maxn],low[maxn],sta[maxn],Top,vis[maxn],col[maxn],A[maxn],bp,r[maxn],tr[maxn];13 struct edge14 {15 int too,nex;16 };17 queue int q;18 19 namespace shzr20 {21 int firs[maxn],h;22 edge g[maxm];23 void add (int x,int y)24 {25 g[h].tooy;26 g[h].nexfirs[x];27 firs[x]h;28 }29 }30 namespace asu31 {32 int firs[maxn],h;33 edge g[maxm];34 void add (int x,int y)35 {36 g[h].tooy;37 g[h].nexfirs[x];38 firs[x]h;39 }40 }41 42 void Tarjan (int x)43 {44 id[x]low[x]cnt;45 sta[Top]x;46 vis[x]1;47 int j;48 for (R ishzr::firs[x];i;ishzr::g[i].nex)49 {50 jshzr::g[i].too;51 if(!id[j])52 {53 Tarjan(j);54 low[x]min(low[x],low[j]);55 }56 else57 {58 if(vis[j]) low[x]min(low[x],id[j]);59 }60 }61 if(low[x]id[x])62 {63 col[x]bp;64 A[bp]a[x];65 vis[x]false;66 while(sta[Top]!x)67 {68 col[ sta[Top] ]bp;69 if(A[bp]-1) A[bp]a[ sta[Top] ];70 else if(a[ sta[Top] ]!-1) A[bp]min(A[bp],a[ sta[Top] ]); 71 vis[ sta[Top] ]false;72 Top--;73 }74 Top--;75 }76 }77 78 int main()79 {80 scanf(%d%d,n,p);81 memset(a,-1,sizeof(a));82 for (R i1;ip;i)83 {84 scanf(%d%d,x,v);85 a[x]v;86 }87 scanf(%d,m);88 for (R i1;im;i)89 {90 scanf(%d%d,x,y);91 shzr::add(x,y);92 }93 for (R i1;in;i)94 if(!id[i]) Tarjan(i);95 int k;96 for (R i1;in;i)97 for (R jshzr::firs[i];j;jshzr::g[j].nex)98 {99 kshzr::g[j].too;
100 if(col[i]col[k]) continue;
101 asu::add(col[i],col[k]);
102 r[ col[k] ];
103 }
104 for (R i1;ibp;i)
105 if(!r[i]) q.push(i);
106 while(q.size())
107 {
108 begq.front();
109 q.pop();
110 if(tr[beg]falseA[beg]!-1) ansA[beg],tr[beg]true;
111 for (R iasu::firs[beg];i;iasu::g[i].nex)
112 {
113 kasu::g[i].too;
114 tr[k]|tr[beg];
115 r[k]--;
116 if(!r[k]) q.push(k);
117 }
118 }
119 for (R i1;in;i)
120 if(tr[ col[i] ]false)
121 {
122 printf(NO\n%d,i);
123 return 0;
124 }
125 printf(YES\n%d,ans);
126 return 0;
127 } 间谍网络 ---shzr转载于:https://www.cnblogs.com/shzr/p/9259695.html
