洛谷3627 [APIO2009]抢掠计划

题意

给出一个有点权的无向图，有的节点有酒吧。从起点出发，需要找到以酒吧为终点的路径，每个节点可以经过任意次，求路径上点权和的最大值。

其中点数 $N\le 500000$ ，边数 $M\le 500000$ 。

题解

缩点，转化为DAG后跑最长路即可。最后取有酒吧的节点中最长路的最大值。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int from,next,to;
} edge[500005],edge2[500005],e[500005];
stack <int> s;
bool have_bar[500005],in[500005],scc_have_bar[500005];
int id[500005],low[500005],scc[500005],wnew[500005],dfsord,scnt;
int cnt,head[500005],cnt2,head2[500005],ecnt,n,m,a,b,st,p,w[500005],dis[500005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].from=u;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void add2(int u,int v)
{
    edge2[++cnt2].to=v;
    edge2[cnt2].from=u;
    edge2[cnt2].next=head2[u];
    head2[u]=cnt2;
}

void dfs(int x)
{
    id[x]=low[x]=++dfsord;
    s.push(x);
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (!id[y])
        {
            dfs(y);
            low[x]=min(low[x],low[y]);
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
    if (id[x]==low[x])
    {
        scnt++;
        while (!s.empty())
        {
            int t=s.top(); s.pop();
            scc[t]=scnt;
            wnew[scnt]+=w[t];
            scc_have_bar[scnt]|=have_bar[t];
            if (x==t) break;
        }
    }
}

inline void init()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        add(a,b);
    }
    for (int i=1;i<=n;i++) w[i]=read();
    st=read(); p=read();
    for (int i=1;i<=p;i++) have_bar[read()]=1;
}

inline bool cmp(Edge x,Edge y) { return (x.from==y.from) ? x.to<y.to : x.from<y.from; }

inline int spfa()
{
    memset(dis,-0x3f,sizeof(dis));
    dis[st]=wnew[st];
    queue <int> q;
    q.push(st);
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        in[x]=0;
        for (int i=head2[x];i;i=edge2[i].next)
        {
            int y=edge2[i].to;
            if (dis[x]+wnew[y]>dis[y])
            {
                dis[y]=dis[x]+wnew[y];
                if (in[y]) continue;
                in[y]=1;
                q.push(y);
            }
        }
    }
    int ans=0;
    for (int i=1;i<=scnt;i++)
    {
        if (!scc_have_bar[i]) continue;
        ans=max(ans,dis[i]);
    }
    return ans;
}

int main()
{
    init();
    for (int i=1;i<=n;i++)
    {
        if (id[i]) continue;
        dfs(i);
    }
    for (int x=1;x<=n;x++)
    {
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (scc[x]==scc[y]) continue;
            e[++ecnt].from=scc[x];
            e[ecnt].to=scc[y];
        }
    }
    sort(e+1,e+ecnt+1,cmp);
    for (int i=1;i<=ecnt;i++)
    {
        if (e[i].from==e[i-1].from && e[i].to==e[i-1].to) continue;
        add2(e[i].from,e[i].to);
    }
    st=scc[st];
    return !printf("%d",spfa());
}