1.一开始写的DP + tarjan

TLE #2 #3

WA #11

2.加哈希DP

WA #2 #3 #11

3.后来把DP换成SPFA

WA #2

TLE #3

dij写炸了

code3:

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define int long long
const int N = 1e5 * 5 + 109;
int h[N], hs[N], e[N], ne[N], idx;
int top, scc_cnt, times;
int stk[N], in_stk[N], low[N], dfn[N];
int w[N], id[N], sz[N];
int f[N];
int din[N], dout[N];
int d[N];
int tag[N];
int endd[N];
int n,m;
queue<int> q;
int in_queue[N];
int s, p;
void add(int h[],int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++ times;
    stk[++ top] = u, in_stk[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int y = e[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[u] = min(low[u], low[y]);
        }
        else if(in_stk[y])
        {
            low[u] = min(low[u], dfn[y]); 
        }
    }

    if(low[u] == dfn[u])
    {
        scc_cnt ++;
        int y;
        do {
            y = stk[top --];
            in_stk[y] = 0;
            id[y] = scc_cnt;
            sz[scc_cnt] += w[y];
            endd[scc_cnt] = endd[scc_cnt] | tag[y]; 
        }while(u != y);
    }
}

signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    for(int i = 1; i <= m; i ++)
    {
        int a,b;
        scanf("%lld%lld", &a, &b);
        add(h,a,b);
    }
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld", &w[i]);
    }
    cin >> s >> p;
    for(int i = 1; i <= p; i ++)
    {
        int x;
        scanf("%lld", &x);

        tag[x] = 1;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i])tarjan(i);
    }
    unordered_set<int> Set;

    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i])continue;
        for(int j = h[i]; ~j; j = ne[j])
        {
            int y = e[j];
            int a = id[i], b = id[y];
            int Q = a * 1000000ll + b;
            if(a != b && !Set.count(Q))
            {
                add(hs, a, b);
                
                Set.insert(Q);
                din[b] ++, dout[a] ++;
            }

        }
    }
   
    d[id[s]] = sz[id[s]];
    q.push(id[s]);
    in_queue[id[s]] = 1;
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        in_queue[x] = 0;
        for(int i = hs[x]; ~i; i = ne[i])
        {
            int y = e[i];
            if(d[y] < d[x] + sz[y])
            {
                d[y] = d[x] + sz[y];
                if(in_queue[y] == 0)
                {
                    in_queue[y] = 1;
                    q.push(y);
                }
            }
        }
    }
    int maxx = 0;
    for(int i = 1; i <= scc_cnt; i ++)
    {
        if(endd[i])
        {
            maxx = max(maxx, d[i]);
        }
    }
    cout << maxx << endl;


    return 0;

}
/*
6 7 
1 2 
2 3 
3 5 
2 4 
4 1 
2 6 
6 5 
10 
12 
8 
16 
1 
5 
1 4 
4 3 5 6
*/

WA #2 #3 #11 的哈希DP

code2:

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define int long long
const int N = 1e5 * 5 + 109;
int h[N], hs[N], e[N], ne[N], idx;
int top, scc_cnt, times;
int stk[N], in_stk[N], low[N], dfn[N];
int w[N], id[N], sz[N];
int f[N];
int din[N], dout[N];
int tag[N];
int endd[N];
int n,m;
int s, p;
void add(int h[],int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++ times;
    stk[++ top] = u, in_stk[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int y = e[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[u] = min(low[u], low[y]);
        }
        else if(in_stk[y])
        {
            low[u] = min(low[u], dfn[y]); 
        }
    }

    if(low[u] == dfn[u])
    {
        scc_cnt ++;
        int y;
        do {
            y = stk[top --];
            in_stk[y] = 0;
            id[y] = scc_cnt;
            sz[scc_cnt] += w[y];
            endd[scc_cnt] = endd[scc_cnt] | tag[y]; 
        }while(u != y);
    }
}

signed main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    for(int i = 1; i <= m; i ++)
    {
        int a,b;
        scanf("%lld%lld", &a, &b);
        add(h,a,b);
    }
    for(int i = 1; i <= n; i ++)
    {
        scanf("%lld", &w[i]);
    }
    cin >> s >> p;
    for(int i = 1; i <= p; i ++)
    {
        int x;
        scanf("%lld", &x);

        tag[x] = 1;
    }
    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i])tarjan(i);
    }
    unordered_set<int> Set;

    for(int i = 1; i <= n; i ++)
    {
        if(!dfn[i])continue;
        for(int j = h[i]; ~j; j = ne[j])
        {
            int y = e[j];
            int a = id[i], b = id[y];
            int Q = a * 1000000ll + b;
            if(a != b && !Set.count(Q))
            {
                add(hs, a, b);
                
                Set.insert(Q);
                din[b] ++, dout[a] ++;
            }

        }
    }
    f[id[s]] = sz[id[s]];
    int maxx = 0;
    queue<int> q;
    int S = id[s];
    //cout << S;
    q.push(S);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        for(int i = hs[x]; ~i; i = ne[i])
        {
            int y = e[i];
            //cout << x << " -> " << y << endl;

            din[y] --;
            if(!din[y])q.push(y);
            f[y] = max(f[y], f[x] + sz[y]);
            if(endd[y])maxx = max(maxx, f[y]);
        }
    }

    cout << maxx << endl;
    return 0;

}
/*
6 7 
1 2 
2 3 
3 5 
2 4 
4 1 
2 6 
6 5 
10 
12 
8 
16 
1 
5 
1 4 
4 3 5 6
*/