(求助)T第三个点
查看原帖
(求助)T第三个点
892323
AkTtt楼主2023/9/21 21:39
#include <iostream>
#include <algorithm>
#include <functional>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <unordered_set>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5e5 + 10;
const int INF=0x3f3f3f3f,mod=998244353;
const LL INFF=0x3f3f3f3f3f3f3f3f;

int t, n, m, dfn[N], low[N], tt, cnt, id[N];
int e[N * 3], ne[N * 3], h[N], hs[N], idx, siz[N];
int w[N], s, p, sp[N], f[N];
bool st[N];
stack<int> stk;

void add(int h[], int x, int y){
    e[idx] = y, ne[idx] = h[x], h[x] = idx++;
}

void tarjan(int x){
    dfn[x] = low[x] = ++tt;
    stk.push(x);
    st[x] = true;

    for(int i = h[x]; i != -1; i = ne[i]){
        int j = e[i];
        if(!dfn[j]){
            tarjan(j);
            low[x] = min(low[x], low[j]);
        }
        else if(st[j])low[x] = min(low[x], low[j]);
    }

    if(dfn[x] == low[x]){
        cnt++;
        ///cout << cnt << endl;
        while(1){
            int k = stk.top();
            stk.pop();
            //cout << k << ' ';
            st[k] = false;
            id[k] = cnt;
            siz[cnt] += w[k];
            if(k == x)break;
        }
        //cout << endl;
        //cout << cnt << ' ' << siz[cnt] << endl;
    }

}

void dfs(int x){
    for(int i = hs[x]; i != -1; i = ne[i]){
        int j = e[i];
        if(f[j] < f[x] + siz[j])f[j] = f[x] + siz[j];
        dfs(j);
        //cout << j << ' ' << f[j] << endl;
    }
}

void solve()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    while(m--){
        int a, b;
        scanf("%d%d", &a, &b);
        add(h, a, b);
    }
    for(int i = 1; i <= n; i++)scanf("%d", &w[i]);

    cin >> s >> p;
    for(int i = 1; i <= p; i++)scanf("%d", &sp[i]);
    for(int i = 1; i <= n; i++){
        if(!dfn[i])tarjan(i);
    }


    unordered_set<LL> ma;
    //map<PII, int> ma;
    for(int j = 1; j <= n; j++){
        for(int i = h[j]; i != -1; i = ne[i]){
            int a = id[j], b = id[e[i]];
            LL s = a * 10000000 + b;
            if(a != b && !ma.count(s)){
                ma.insert(s);
                add(hs, a, b);
            }
        }
    }

    f[id[s]] = siz[id[s]];
    dfs(id[s]);

    int ans = 0;
    for(int i = 1; i <= p; i++){
        ans = max(ans, f[id[sp[i]]]);
    }

    cout << ans << endl;
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    // cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}
2023/9/21 21:39
加载中...