【强联通分量缩点】【最短路】【spfa】bzoj1179 [Apio2009]Atm

浏览数：47 / 时间：2015年06月11日

缩点后转化成 DAG图上的单源最长路问题。spfa/dp随便。

 1 #include<cstdio>
 2 #include<queue>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstring>
 6 using namespace std;
 7 int cmp[500001],sum,n,m,Us[500001],Vs[500001],t,w[500001],sta,k,ans,dis[500001];
 8 bool vis[500001],inq[500001];
 9 struct Edge{int v,w;Edge(const int &a,const int &b){v=a;w=b;}Edge(){}};
10 vector<int>G[500001],rG[500001],G2[500001],vs;
11 typedef vector<int>::iterator ITER;
12 queue<int>q;
13 void dfs(int U)
14 {
15     vis[U]=1;
16     for(ITER it=G[U].begin();it!=G[U].end();++it) if(!vis[*it]) dfs(*it);
17     vs.push_back(U);
18 }
19 void dfs2(int U)
20 {
21     cmp[U]=sum;
22     for(ITER it=rG[U].begin();it!=rG[U].end();++it) if(!cmp[*it]) dfs2(*it);
23 }
24 void scc()
25 {
26     for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
27     ITER it=vs.end(); --it;
28     for(;;it--)
29       {
30         if(!cmp[*it]) {++sum; dfs2(*it);}
31         if(it==vs.begin()) break;
32       }
33 }
34 void spfa(const int &s)
35 {
36     dis[s]=w[s]; q.push(s); inq[s]=1;
37     while(!q.empty())
38       {
39         int U=q.front();
40         for(ITER it=G2[U].begin();it!=G2[U].end();it++)
41           if(dis[*it]<dis[U]+w[*it])
42             {
43               dis[*it]=dis[U]+w[*it];
44               if(!inq[*it])
45                 {
46                   q.push(*it);
47                   inq[*it]=1;
48                 }
49             }
50         q.pop(); inq[U]=0;
51       }
52 }
53 int main()
54 {
55     scanf("%d%d",&n,&m);
56     for(int i=1;i<=m;++i)
57       {
58           scanf("%d%d",&Us[i],&Vs[i]);
59           G[Us[i]].push_back(Vs[i]);
60           rG[Vs[i]].push_back(Us[i]);
61       } scc();
62     for(int i=1;i<=n;++i) {scanf("%d",&t); w[cmp[i]]+=t;}
63     for(int i=1;i<=m;++i)
64       if(cmp[Us[i]]!=cmp[Vs[i]])
65         G2[cmp[Us[i]]].push_back(cmp[Vs[i]]);
66     scanf("%d%d",&sta,&k);
67     spfa(cmp[sta]);
68     for(int i=1;i<=k;++i)
69       {
70           scanf("%d",&t);
71           ans=max(dis[cmp[t]],ans);
72       } printf("%d\n",ans);
73     return 0;
74 }