记录编号	342086	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.739 s
提交时间	2016-11-08 09:08:30	内存使用	0.30 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 500001
class Graph
{
    vector<int> G[MAX];
    vector<int> GS[MAX];
    vector<int> sccp[MAX];
    int low[MAX];
    int dfn[MAX];
    int w[MAX];
    int stk[MAX];
    int scc[MAX];
    int sccw[MAX];
    bool is_fin[MAX];
    bool scc_fin[MAX];
    int scc_cnt;
    int stktop;
    int time_stamp;
    int n;
    int s;
public:
    Graph(int n_nodes)
    {
        memset(low, 0, sizeof(low));
        memset(dfn, 0, sizeof(dfn));
        memset(scc, 0, sizeof(scc));
        memset(is_fin, false, sizeof(is_fin));
        memset(sccw, 0, sizeof(sccw));
        time_stamp = 1;
        stktop = 0;
        scc_cnt = 0;
        n = n_nodes;
    }
    inline void addedge(int u, int v)
    {
        G[u].push_back(v);
    }
    void tarjan(int u)
    {
        dfn[u] = low[u] = ++time_stamp;
        stk[stktop++] = u;
        for(int i = 0; i < G[u].size(); i++)
        {
            int to = G[u][i];
            if(!dfn[to])
            {
                tarjan(to);
                low[u] = min(low[u], low[to]);
            }else if(!scc[to])
            {
                low[u] = min(low[u], dfn[to]);
            }
        }
        if(low[u] == dfn[u])
        {
            int x;
            scc_cnt++;
            while(true)
            {
                x = stk[--stktop];
                sccp[scc_cnt].push_back(x);
                scc[x] = scc_cnt;
                sccw[scc_cnt] += w[x];
                if(is_fin[x])scc_fin[scc_cnt] = true;
                if(x == u || !stktop)break;
            }
        }
    }
    void make_GS()
    {
        for(int i = 1; i <= n; i++)
            if(!dfn[i])tarjan(i);
        for(int i = 1; i <= scc_cnt; i++)
        {
            for(int j = 0; j < sccp[i].size(); j++)
            {
                int u = sccp[i][j];
                for(int k = 0; k < G[u].size(); k++)
                {
                    int t = G[u][k];
                    if(scc[t] != i)
                        GS[i].push_back(scc[t]);
                }
            }
        }
        
    }
    int ans;
    bool vis[MAX];
    int dist[MAX];
    void spfa()
    {
        int sp = scc[s];
        dist[sp] = sccw[sp];
        queue<int> q;
        q.push(sp);
        while(!q.empty())
        {
            int u = q.front();
            q.pop();
            for(int i = 0; i < GS[u].size(); i++)
            {
                int to = GS[u][i];
                if(dist[to] < dist[u]+sccw[to])
                {
                    dist[to] = sccw[to]+dist[u];
                    if(!vis[to])
                    {
                        q.push(to);
                        vis[to] = true;
                    }
                }
            }
            vis[u] = false;
        }
        for(int i = 1; i <= scc_cnt; i++)
            if(scc_fin[i])ans = max(ans, dist[i]);
    }
    void result()
    {
        ans = 0;
        memset(vis, false, sizeof(vis));
        memset(dist, 0, sizeof(dist));
        spfa();
        printf("%d\n", ans);
    }
    inline void set_s(int st)
    {
        s = st;
    }
    inline void input_w()
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", w+i);
    }
    inline void input_p(int p)
    {
        for(int i = 1; i <= p; i++)
        {
            int x;
            scanf("%d", &x);
            is_fin[x] = true;
        }
    }
};

int main()
{
    freopen("atm.in", "r", stdin);
    freopen("atm.out", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);
    Graph *g = new Graph(n);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        g->addedge(a, b);
    }
    g->input_w();
    int s, p;
    scanf("%d %d", &s, &p);
    g->set_s(s);
    g->input_p(p);
    g->make_GS();
    g->result();
    delete g;
    return 0;
}