【题解】洛谷P3627 [APIO2009]抢掠计划（缩点+SPFA）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

洛谷P3627：https://www.luogu.org/problemnew/show/P3627

思路

由于有强连通分量所以我们可以想到先把整个图缩点

缩点完之后再建一次图把 点权改为边权 并把边权转为负数即可用 SPFA求最短路 间接求最长路了

最后我们查询所有的酒吧跳出最大的ans即可

思路简单但是代码有些冗长

代码

#include<iostream>

#include<cstring>

using namespace std;

#define maxn 500010

int n,m,s,p,top,num,cnt,col,ans,t,w;

int h[maxn],de[maxn],st[maxn],dfn[maxn],low[maxn],co[maxn],money[maxn],sum[maxn],q[maxn],dis[maxn],x[maxn],y[maxn];

bool vis[maxn],exist[maxn];

struct Edge

{

    int to;

    int next;

    int w;

}e[maxn];

void add(int u,int v)//Tarjan的边

{

    e[++cnt].to=v;

    e[cnt].next=h[u];

    h[u]=cnt;

}

void read()//输入

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        cin>>x[i]>>y[i];

        add(x[i],y[i]);

    }

    for(int i=;i<=n;i++)

    cin>>money[i];

    cin>>s;

}

void Add(int u,int v,int w)//SPFA的边

{

    e[++cnt].w=w;

    e[cnt].to=v;

    e[cnt].next=h[u];

    h[u]=cnt;

}

void Tarjan(int u)//标准Tarjan

{

    dfn[u]=low[u]=++num;

    vis[u]=;

    st[++top]=u;

    for(int i=h[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(!dfn[v])

        {

            Tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else

        if(vis[v])

        {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(dfn[u]==low[u])

    {

        col++;

        while(st[top+]!=u)

        {

            sum[col]+=money[st[top]];//计算此强连通分量的总价值

            co[st[top]]=col;

            vis[st[top--]]=;

        }

    }

}

void SPFA()//标准SPFA

{

    memset(dis,,sizeof(dis));

    dis[co[s]]=-sum[co[s]];//负权

    q[]=co[s];//把市中心所在的点入队

    t=;

    w=;

    while(t<w)

    {

        t++;

        int u=q[t];

        exist[u]=;

        for(int i=h[u];i;i=e[i].next)

        {

            int v=e[i].to;

            if(dis[v]>dis[u]+e[i].w)

            {

                dis[v]=dis[u]+e[i].w;

                if(!exist[v])

                {

                    w++;

                    q[w]=v;

                    exist[v]=;

                }

            }

        }

    }

}

int main()

{

    read();

    for(int i=;i<=n;i++)

    if(!dfn[i]) Tarjan(i);

    cnt=;

    memset(e,,sizeof(e));

    memset(h,,sizeof(h));//注意清空边

    for(int i=;i<=m;i++)

        if(co[x[i]]!=co[y[i]])

        Add(co[x[i]],co[y[i]],-sum[co[y[i]]]);//负权边

    SPFA();

    cin>>p;

    for(int i=;i<=p;i++)//枚举所有酒吧求最大值

    {

        int bar;

        cin>>bar;

        if(-dis[co[bar]]>ans)

        ans=-dis[co[bar]];

    }

    cout<<ans;

}