【洛谷P3627】[APIO2009]抢掠计划

抢掠计划

比较水的缩点模板题，Tarjan缩点，重新建图，记录联通块的钱数、是否有酒吧
DAG上记忆化搜索即可
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 #define N 500010
 6 inline int read(){
 7     int x=0; char c=getchar();
 8     while(c<'0'||c>'9') c=getchar();
 9     while('0'<=c&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
10     return x;
11 }
12 int n,m,s,p,val[N],Val[N];
13 int head[N],to[N],next[N],sume;
14 bool ins[N],bar[N],Bar[N];
15 int dfn[N],low[N],stack[N],top,cnt,num;
16 int belong[N],Head[N],To[N],Next[N],Sume;
17 int f[N];
18 inline void add(int x,int y){
19     to[++sume]=y;
20     next[sume]=head[x];
21     head[x]=sume;
22 }
23 inline void Add(int x,int y){
24     To[++Sume]=y;
25     Next[Sume]=Head[x];
26     Head[x]=Sume;
27 }
28 inline void dfs(int t){　　//Tarjan缩点
29     dfn[t]=low[t]=++cnt;
30     ins[t]=1; stack[++top]=t;
31     for(int i=head[t];i;i=next[i]){
32         int v=to[i];
33         if(!dfn[v]){
34             dfs(v);
35             low[t]=min(low[t],low[v]);
36         }
37         else if(ins[v])
38             low[t]=min(low[t],dfn[v]);
39     }
40     if(low[t]==dfn[t]){
41         num++;
42         while(stack[top]!=t){
43             int k=stack[top];
44             belong[k]=num;
45             ins[k]=0;
46             if(bar[k]) Bar[num]=1;
47             Val[num]+=val[k];
48             top--;
49         }
50         belong[t]=num;
51         ins[t]=0;
52         if(bar[t]) Bar[num]=1;
53         Val[num]+=val[t];
54         top--;
55     }
56 }
57 bool dfs2(int u){　　　　//记忆化搜索
58     if(f[u]) return f[u];
59     int maxx=0; bool flag=Bar[u];
60     for(int i=Head[u];i;i=Next[i])
61      if(dfs2(To[i])){
62          flag=1;
63          maxx=max(maxx,f[To[i]]);
64      }
65     if(flag) f[u]=maxx+Val[u];
66     else f[u]=0;
67     return flag;
68 }
69 int main()
70 {
71     n=read(); m=read();
72     int x,y;
73     for(int i=1;i<=m;i++){
74         x=read(); y=read();
75         add(x,y);
76     }
77     for(int i=1;i<=n;i++)
78      val[i]=read();
79     s=read(); p=read();
80     for(int i=1;i<=p;i++){
81         x=read();
82         bar[x]=1;
83     }
84     dfs(s);
85     for(int u=1;u<=n;u++)　　　　//重新建图
86      for(int j=head[u];j;j=next[j]){
87          int v=to[j];
88          if(belong[u]!=belong[v])
89           Add(belong[u],belong[v]);
90      }
91     dfs2(belong[s]);
92     printf("%d",f[belong[s]]);
93     return 0;
94 }