BZOJ 1179 Atm(强连通分量缩点+DP)

题目说可以通过一条边多次，且点权是非负的，所以如果走到图中的一个强连通分量，那么一定可以拿完这个强连通分量上的money。

所以缩点已经很明显了。缩完点之后图就是一个DAG，对于DAG可以用DP来求出到达每一个点的money最大值。具体实现我用的是bfs。

然后如果一个强连通分量内有酒馆，那么这个点就可以更新答案啦。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct Edge{int p, next;}edge[N], edge1[N];

int head[N], head1[N], cnt=, cnt1=, node[N], ans=, dis[N];

int Low[N], DFN[N], Stack[N], Belong[N], Index, top, scc, num[N];

bool Instack[N], isjiu[N], jiu[N];

queue<int>Q;

void add_edge(int u, int v){edge[cnt].p=v; edge[cnt].next=head[u]; head[u]=cnt++;}

void add_edge1(int u, int v){edge1[cnt1].p=v; edge1[cnt1].next=head1[u]; head1[u]=cnt1++;}

void Tarjan(int u)

{

    int v;

    Low[u]=DFN[u]=++Index; Stack[top++]=u; Instack[u]=true;

    for (int i=head[u]; i; i=edge[i].next) {

        int v=edge[i].p;

        if (!DFN[v]) {

            Tarjan(v);

            if (Low[u]>Low[v]) Low[u]=Low[v];

        }

        else if (Instack[v]&&Low[u]>DFN[v]) Low[u]=DFN[v];

    }

    if (Low[u]==DFN[u]) {

        scc++;

        do{

            v=Stack[--top]; Instack[v]=false; Belong[v]=scc;

            num[scc]+=node[v]; jiu[scc]|=isjiu[v];

        }while (v!=u);

    }

}

void solve(int n){

    mem(DFN,); mem(Instack,); mem(num,);

    Index=scc=top=;

    FOR(i,,n) if (!DFN[i]) Tarjan(i);

}

int main ()

{

    int n, m, u, v, s, p;

    n=Scan(); m=Scan();

    while (m--) u=Scan(), v=Scan(), add_edge(u,v);

    FOR(i,,n) node[i]=Scan();

    s=Scan(); p=Scan();

    FOR(i,,p) u=Scan(), isjiu[u]=;

    solve(n);

    FO(i,,n) for (u=head[i]; u; u=edge[u].next) {

        v=edge[u].p;

        if (Belong[v]==Belong[i]) continue;

        add_edge1(Belong[i],Belong[v]);

    }

    Q.push(Belong[s]); dis[Belong[s]]=num[Belong[s]];

    while (!Q.empty()) {

        u=Q.front(); Q.pop();

        if (jiu[u]) ans=max(ans,dis[u]);

        for (int i=head1[u]; i; i=edge1[i].next) {

            v=edge1[i].p;

            if (dis[v]>=dis[u]+num[v]) continue;

            dis[v]=dis[u]+num[v];

            Q.push(v);

        }

    }

    printf("%d\n",ans);

    return ;

}