P3627 [APIO2009]抢掠计划

#include
#include
#include
#include
#includeusing namespace std;
template  inline T min(T &a,T &b) {return aa:b;}
template  inline T max(T &a,T &b) {return a>b ?a:b;}
template  inline void read(T &x){
    char c=getchar(); x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x3)+(x1)+(c^48),c=getchar();
}
queue int> h;
const int N=1000002;
int n,m,s,p,dfs_clock,dfn[N],low[N],tot,be[N],_top,st[N];
int val1[N],cnt,hd[N],nxt[N],ed[N],poi[N];
int val2[N],cnt2,hd2[N],nxt2[N],ed2[N],poi2[N];
int d[N]; bool bar1[N],bar2[N],vis[N];
inline void add(int x,int y){
    nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt;
    ed[x]=cnt; poi[cnt]=y;
}
inline void add2(int x,int y){
    nxt2[ed2[x]]=++cnt2; hd2[x]= hd2[x] ? hd2[x]:cnt2;
    ed2[x]=cnt2; poi2[cnt2]=y;
}
inline void tarjan(int x){
    dfn[x]=low[x]=++dfs_clock; st[++_top]=x;
    for(int i=hd[x];i;i=nxt[i]){
        if(!dfn[poi[i]]) tarjan(poi[i]),low[x]=min(low[x],low[poi[i]]);
        else if(!be[poi[i]]) low[x]=min(low[x],dfn[poi[i]]);
    }
    if(dfn[x]==low[x]){
        be[x]=++tot; val2[tot]=val1[x];
        while(st[_top]!=x) be[st[_top]]=tot,val2[tot]+=val1[st[_top--]]; //维护总权值
        --_top;
    }
}
int spfa(){
    h.push(be[s]); vis[be[s]]=1;
    while(!h.empty()){
        int x=h.front(); h.pop(); vis[x]=0;
        for(register int i=hd2[x];i;i=nxt2[i])
            if(d[x]+val2[x]>d[poi2[i]]){ //最长路
                d[poi2[i]]=d[x]+val2[x];
                if(!vis[poi2[i]]) h.push(poi2[i]),vis[poi2[i]]=1;
            }
    }int ans=0;
    for(register int i=1;ii) //枚举有酒吧的强连通分量
        if(bar2[i])
            ans=max(ans,d[i]+val2[i]);
    return ans;
}
int main(){
    read(n); read(m); int q1,q2;
    for(register int i=1;ii) read(q1),read(q2),add(q1,q2);
    for(register int i=1;ii) read(val1[i]);
    read(s); read(p);
    for(register int i=1;i1;
    for(register int i=1;iif(!dfn[i]) tarjan(i);
    for(register int i=1;ii){
        if(bar1[i]) bar2[be[i]]=1; //给新图做上是否有酒吧的标记
        for(register int j=hd[i];j;j=nxt[j])
            if(be[i]!=be[poi[j]])
                add2(be[i],be[poi[j]]);
    }printf("%d",spfa());
    return 0;
}