Tarjan缩点模板(P3627 [APIO2009]抢掠计划题解)

  1 //
  2 //  P3627 [APIO2009]抢掠计划.cpp
  3 //  7.22作业
  4 //
  5 //  Created by skygao on 2019/7/22.
  6 //  Copyright © 2019 skygao. All rights reserved.
  7 //
  8 
  9 #include <stdio.h>
 10 #include <cstdlib>
 11 #include <cstring>
 12 #include <string>
 13 #include <iostream>
 14 #include <algorithm>
 15 #include <vector>
 16 #include <queue>
 17 #define maxn 500005
 18 #define re register
 19 using namespace std;
 20 int dfsn[maxn],lowlink[maxn],dfs_clock;
 21 int stack[maxn],top,scc[maxn],scc_cnt;//scc_cnt有多少个强连通分量,scc[maxn]每个点在哪个强连通分量里
 22 vector<int> son[maxn],v[maxn];
 23 int val[maxn],sum[maxn];
 24 int dis[maxn],ans;
 25 int x[maxn],y[maxn];
 26 int n,m,s,p;
 27 bool vis[maxn];
 28 inline void dfs_scc(int x)//tarjan
 29 {
 30     dfsn[x]=lowlink[x]=++dfs_clock;
 31     stack[++top]=x;
 32     for(re int i=0;i<son[x].size();++i)
 33     {
 34         int now=son[x][i];
 35         if(!dfsn[now])
 36         {
 37             dfs_scc(now);
 38             lowlink[x]=min(lowlink[x],lowlink[now]);
 39         }
 40         else if(!scc[now])
 41             lowlink[x]=min(lowlink[x],lowlink[now]);
 42     }
 43     if(lowlink[x]==dfsn[x])
 44     {
 45         scc_cnt++;
 46         while(stack[top+1]!=x)
 47         {
 48             scc[stack[top]]=scc_cnt;
 49             sum[scc_cnt]+=val[stack[top--]];
 50         }
 51     }
 52 }
 53 inline void addedge(int x,int y)//建图跑tarjan
 54 {
 55     son[x].push_back(y);
 56 }
 57 inline void _addedge(int x,int y,int val)//建图跑SPFA
 58 {
 59     son[x].push_back(y);
 60     v[x].push_back(val);
 61 }
 62 queue<int> q;
 63 void spfa()
 64 {
 65     memset(dis,0x7f,sizeof(dis));
 66     int tmp=scc[s];
 67     dis[tmp]=-sum[tmp];
 68     q.push(tmp);vis[tmp]=true;
 69     while(!q.empty())
 70     {
 71         int prt=q.front();
 72         q.pop();
 73         for(re int i=0;i<son[prt].size();++i)
 74         {
 75             int rt=son[prt][i];
 76             if(dis[prt]+v[prt][i]<dis[rt])
 77             {
 78                 dis[rt]=dis[prt]+v[prt][i];
 79                 if(!vis[rt])
 80                 {
 81                     q.push(rt);
 82                     vis[rt]=true;
 83                 }
 84             }
 85         }
 86         vis[prt]=false;
 87     }
 88 }
 89 int main()
 90 {
 91     scanf("%d%d",&n,&m);
 92     for(re int i=1;i<=m;++i)
 93     {
 94         scanf("%d%d",&x[i],&y[i]);
 95         addedge(x[i],y[i]);
 96     }
 97     for(re int i=1;i<=n;++i)
 98         scanf("%d",&val[i]);
 99     for(re int i=1;i<=n;++i)
100         if(!dfsn[i])
101             dfs_scc(i);
102     for(re int i=1;i<=n;++i)
103         son[i].clear();
104     for(re int i=1;i<=m;++i)
105         if(scc[x[i]]!=scc[y[i]])
106             _addedge(scc[x[i]],scc[y[i]],-sum[scc[y[i]]]);//建图，点权变负跑最短路
107     scanf("%d%d",&s,&p);
108     spfa();
109     for(re int i=1;i<=p;++i)//找每一个酒吧并计算，求最大值
110     {
111         int tmp;
112         scanf("%d",&tmp);
113         if(-dis[scc[tmp]]>ans)
114             ans=-dis[scc[tmp]];
115     }
116     printf("%d",ans);
117     return 0;
118 }