WA 56pts 求助
查看原帖
WA 56pts 求助
425007
Kappa6174楼主2021/4/19 21:03
#include<bits/stdc++.h>
#define Maxn 500300
#define int long long
using namespace std;
int cnt;
struct EDGE{
    int to;
    int nxt;
    int v;
}Old[Maxn*2];
EDGE New[Maxn*2];
EDGE Anti[Maxn*2];
int Head[Maxn];
int a[Maxn];
bool f[Maxn];
bool Newf[Maxn];
int Nhead[Maxn];
int Ahead[Maxn];
int v[Maxn];
bool vis[Maxn];
int col[Maxn];
int Ncnt;
int Acnt,rt,P;
int Col;
int dfn[Maxn];
int rd[Maxn];
queue<int> q;
int top;
int dp[Maxn];
void dfs1(int p)
{
    vis[p]=1;
    for(int i=Head[p];i;i=Old[i].nxt)
    {
        int k=Old[i].to;
        if(!vis[k])
        {
            dfs1(k);
        }
    }
    dfn[++top]=p;
    return;
}
void dfs2(int p,int c)
{
    vis[p]=1;
    col[p]=c;
    for(int i=Ahead[p];i;i=Anti[i].nxt)
    {
        int k=Anti[i].to;
        if(!vis[k])
        {
            dfs2(k,c);
        }
    }
    return;
}
void Topo()
{
    while(!q.empty())
    {
        int p=q.front();
        vis[p]=1;
        q.pop();
        for(int i=Nhead[p];i;i=New[i].nxt)
        {
            int k=New[i].to;
            //cout<<p<<' '<<k<<'\n';
            if(!vis[k])
            {dp[k]=max(dp[k],dp[p]+v[k]);
            rd[k]--;
            if(!rd[k])q.push(k),vis[k]=1;}
        }
    }
}
int build(int from,int to,EDGE *e,int CNT,int *head)
{
    e[++CNT].to=to;e[CNT].nxt=head[from];head[from]=CNT;return CNT;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i){int u,v;cin>>u>>v;cnt=build(u,v,Old,cnt,Head);
    Acnt=build(v,u,Anti,Acnt,Ahead);}
    for(int i=1;i<=n;++i){cin>>a[i];}
    cin>>rt;cin>>P;
    dfs1(rt);
    for(int i=1;i<=n;++i)vis[i]=0;
    for(int i=top;i>=1;--i)if(!vis[dfn[i]]){++Col;dfs2(dfn[i],Col);}
    for(int i=1;i<=P;++i){int tmp;cin>>tmp;f[tmp]=1;}
    for(int i=1;i<=n;++i)
    {
       // cout<<i<<' '<<col[i]<<'\n';
        int x=col[i];
        v[x]+=a[i];
        Newf[x]|=f[i];
        vis[i]=0;
    }
    for(int i=1;i<=cnt;++i){int x=Anti[i].to;int y=Old[i].to;
    if(col[x]!=col[y]&&col[x]!=0&&col[y]!=0){Ncnt=build(col[x],col[y],New,Ncnt,Nhead);rd[col[y]]++;} }
    for(int i=1;i<=Col;++i)
    {
       // cout<<i<<' '<<v[i]<<' '<<Newf[i]<<' '<<rd[i]<<'\n';
        if(rd[i]==0){q.push(i);dp[i]=v[i];}
    }
    Topo();
    int mx=-1;
    for(int i=1;i<=Col;++i)
    {
       // cout<<i<<'!'<<dp[i]<<'\n';
        if(Newf[i]){mx=max(mx,dp[i]);}
    }
    cout<<mx;
    return 0;
}

史山代码谅解(

2021/4/19 21:03
加载中...