[APIO 2009] Atm

传送门：>Here<

解题思路：

　　题目有点难懂。首先如果只是暴力搜索的话，由于有环会无限循环，而且环内的值只会加一次，很容易想到强连通分量缩点。然后SPFA（改一改，变成最大值）求出每个点的最大值就可以了。然而如果某一个强连通分量里有酒吧，那么走到这个强联通分量作为终点一定是可以的。因此加个判断就好了。还是很水的……

Code

　　Nothing

/*By QiXingzhi*/

#include <cstdio>

#include <queue>

#include <cstring>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

typedef long long ll;

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();

    return x * w;

}

bool bar[MAXN];

queue <int> q;

vector <int> G[MAXN],G2[MAXN];

int N,M,dfs_clock,S,P,scc_cnt,top,_x,ans;

int p[MAXN],sccno[MAXN],dfn[MAXN],low[MAXN],sta[MAXN],x[MAXN],y[MAXN],d[MAXN],val[MAXN],win[MAXN];

inline void AddEdge(int u, int v){ G[u].push_back(v); }

inline void AddEdge2(int u, int v){ G2[u].push_back(v); }

inline void tarjan(int u){

    dfn[u] = low[u] = ++dfs_clock;

    sta[++top] = u;

    int sz = G[u].size(), v;

    for(int i = ; i < sz; ++i){

        v = G[u][i];

        if(!dfn[v]){ tarjan(v); low[u] = Min(low[u], low[v]); }

        else if(!sccno[v]) low[u] = Min(low[u], dfn[v]);

    }

    int X;

    if(dfn[u] == low[u]){

        ++scc_cnt;

        while(){

            X = sta[top--];

            if(bar[X]) win[scc_cnt] = ;

            sccno[X] = scc_cnt;

            val[scc_cnt] += p[X];

            if(X == u) break;

        }

    }

}

inline void BFS(int s){

    d[s] = val[s];

    q.push(s);

    int cur,sz,v;

    while(!q.empty()){

        cur = q.front(), q.pop();

        sz = G2[cur].size();

        for(int i = ; i < sz; ++i){

            v = G2[cur][i];

            if(d[cur] + val[v] > d[v]){ d[v] = d[cur] + val[v]; q.push(v); }

        }

    }

}

int main(){

    N = r, M = r;

    for(int i = ; i <= M; ++i){ x[i] = r, y[i] = r; AddEdge(x[i], y[i]); }

    for(int i = ; i <= N; ++i) p[i] = r;

    S = r, P = r;

    for(int i = ; i <= P; ++i) _x = r, bar[_x] = ;

    for(int i = ; i <= N; ++i) if(!dfn[i]) tarjan(i);

    for(int i = ; i <= M; ++i) if(sccno[x[i]] != sccno[y[i]]) AddEdge2(sccno[x[i]], sccno[y[i]]);

    BFS(sccno[S]);

    for(int i = ; i <= N; ++i) if(win[i]) ans = Max(ans, d[i]);

    printf("%d", ans);

    return ;

}