題目傳送門:https://www.luogu.org/problemnew/show/P3627
題解:tarjan強連通分量縮點+bfsspfa
代碼如下:
1 #include<cstdio>
2 #include<iostream>
3 #define MN 1000010
4 using namespace std;
5 int n,m,w[MN],bar[MN],S,P,ans,hd[MN],cnt,sz[MN],CN,dis[MN],s[MN];
6 int dye[MN],q[MN],top,dfn[MN],low[MN],dfs_ct,re_ct,re_hd[MN];
7 bool vis[MN];
8 struct node{int to,nex,d;}e[MN],re_e[MN];
9 void add(int x,int y){e[++cnt].to=y;e[cnt].nex=hd[x];hd[x]=cnt;}
10 void tarjan(int x){
11 vis[q[++top]=x]=true;
12 dfn[x]=low[x]=++dfs_ct;
13 for(int i=hd[x];i;i=e[i].nex){
14 if(!dfn[e[i].to]){
15 tarjan(e[i].to);
16 low[x]=min(low[x],low[e[i].to]);
17 }
18 else if(vis[e[i].to])
19 low[x]=min(low[x],dfn[e[i].to]);
20 }
21 if(dfn[x]==low[x]){
22 vis[x]=false;
23 sz[dye[x]=++CN]+=w[x];
24 while(x!=q[top]){
25 sz[dye[q[top]]=CN]+=w[q[top]];
26 vis[q[top--]]=false;
27 }
28 --top;
29 }
30 }
31 void rebuild(){
32 for(int i=1;i<=n;++i)
33 for(int j=hd[i];j;j=e[j].nex)
34 if(dye[i]!=dye[e[j].to]&&dye[i]&&dye[e[j].to]){
35 re_e[++re_ct].to=dye[e[j].to];
36 re_e[re_ct].d=sz[dye[e[j].to]];
37 re_e[re_ct].nex=re_hd[dye[i]];
38 re_hd[dye[i]]=re_ct;
39 }
40 }
41 bool spfa(int u){
42 int head=1,tail=1; s[1]=u;
43 while(head<=tail){
44 u=s[head++];
45 for(int i=re_hd[u];i;i=re_e[i].nex){
46 int v=re_e[i].to;
47 if(re_e[i].d+dis[u]>dis[v]){
48 dis[v]=re_e[i].d+dis[u];
49 s[++tail]=v;
50 }
51 }
52 }
53 }
54 int main()
55 {
56 scanf("%d%d",&n,&m);
57 for(int i=1;i<=m;i++){
58 int x,y; scanf("%d%d",&x,&y);
59 add(x,y);
60 }
61 for(int i=1;i<=n;i++) scanf("%d",&w[i]);
62 scanf("%d%d",&S,&P);
63 for(int i=1;i<=P;i++){
64 int x; scanf("%d",&x);
65 bar[x]=true;
66 }
67 for(int i=1;i<=n;i++)if(!dye[i]) tarjan(i);
68 rebuild();
69 dis[dye[S]]=sz[dye[S]];
70 spfa(dye[S]);
71 for(int i=1;i<=n;i++)
72 if(bar[i])if(dis[dye[i]]>ans) ans=dis[dye[i]];
73 printf("%d",ans);
74 return 0;
75 }
轉載于:https://www.cnblogs.com/Beginner-/p/8795716.html