[luoguP3627][APIO2009]抢掠计划

时间：2021-08-07 02:47:08

先来看一下题目描述：

题目描述

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆 祝他的胜利。

使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机 里面就不会再有钱了。 例如，假设该城中有 6 个路口，道路的连接情况如下图所示：

[luoguP3627][APIO2009]抢掠计划

市中心在路口 1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表

示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢 劫的现金总数为 47，实施的抢劫路线是：1-2-4-1-2-3-5。

输入输出格式

输入格式：

第一行包含两个整数 N、M。N 表示路口的个数，M 表示道路条数。接下来 M 行，每行两个整数，这两个整数都在 1 到 N 之间，第 i+1 行的两个整数表示第 i 条道路的起点和终点的路口编号。接下来 N 行，每行一个整数，按顺序表示每 个路口处的 ATM 机中的钱数。接下来一行包含两个整数 S、P，S 表示市中心的 编号，也就是出发的路口。P 表示酒吧数目。接下来的一行中有 P 个整数，表示 P 个有酒吧的路口的编号。

输出格式：

输出一个整数，表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多 的现金总数。

好了，以上是题目描述qwq。

那么现在我们考虑一下用什么方法来做这道题。

首先我们明确一点：这是一个有向有环图。所以我们就应该考虑Tarjan之类的用以处理有向图的方法了。

按照最初的印象，我们好像应该是要跑一次最长路，SPFA完全可以做到这一点。但是我们要知道，他有两个特殊条件：

　　1.没有边权，只有点权，也没有消耗。并且我们是要从这个图里面获得最大的点权，也就是说：边可以走好多次，但是点走一次之后就变为了0。

　　2.我们最后要回到某一个指定的位置。所以SPFA就十分方便。

所以在经过反复思考后，我们决定用Tarjan解决这个问题。那么为什么呢？

因为Tarjan可以很好地解决关于图的连通性的问题。 由此，我们就可以把一个环缩成一个点。

因为我们知道，一旦我们进入了一个环，由于不计费用，所以我们最佳的方案就是直接跑完这个环。就像样例中的1，2，4一样。

好了接下来讲一下如何实现。

1.首先用Tarjan将所有的环所称一个点。

2.跑一边最长路SPFA。

（好像根本没有什么总结的必要emmmm......）

那么接下来是各段的代码。

#define MAXN 100010
int Yeasion[MAXN];//DFS时搜索的顺序。
int Nein[MAXN];//Nein[i]就是表示在当前i节点能够回到的最大的节点处。
bool flag[MAXN];//是否在栈里面
int belong[MAXN];//表示i节点在Tarjan之后属于什么节点。
int value[MAXN];//表示Tarjan之前的节点的价值
int behind_value[MAXN];//表示Tarjan之后的节点价值
int stack[MAXN],cnt,top，ken;//......
vector<int> line[MAXN];//使用不定长数组代替前向星，好像会简洁一点emmmm.....
void Tarjan(int now)
{
    //一下是固定不变的Tarjan  qwq
    Nein[now]=Yeasion[now]=++ken;
    stack[++top]=now;
    flag[now]=true;
    ;i<line[now].size();i++)
    {
        int next=line[now][i];
        if(!Yeasion[next])
        {
            Tarjan(next);
            if(Nein[next]<Nein[now])
                Nein[now]=Nein[next];
        }
        else
            if(flag[next])
            Nein[now]=min(Yeasion[next],Nein[now]);
    }
    if(Nein[now]==Yeasion[now])
    {
        cnt++;//这里我们在Tarjan之后新建了一个图，然后我们资金编造了一个顺序。
        int pass;//顾名思义，过去的节点嘛...
        do
        {
            pass=stack[top--];//更新pass，进行退栈操作。
            belong[pass]=cnt;//表明原图中的pass点属于新图中的cnt节点。
            behind_value[cnt]+=value[pass];//更新新图中的cnt的节点大小
            flag[pass]=false;//退栈.....
        }while(pass!=now);
    }
    return ;
}

然后我们跑一边SPFA就可以了。下面上全部代码。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define MAXN 100001
using namespace std;

int n,m,s,p;

//SPFA用
];
queue<int>q;
];

//Tarjan用
int Yeasion[MAXN];//DFS时搜索的顺序。
int Nein[MAXN];//Nein[i]就是表示在当前i节点能够回到的最大的节点处。
bool flag[MAXN];//是否在栈里面
int belong[MAXN];//表示i节点在Tarjan之后属于什么节点。
int value[MAXN];//表示Tarjan之前的节点的价值
int behind_value[MAXN];//表示Tarjan之后的节点价值
int stack[MAXN],cnt,top,ken;//......
vector<int> line[MAXN];//使用不定长数组代替前向星，好像会简洁一点emmmm.....
vector<];
];
void Tarjan(int now)
{
    //一下是固定不变的Tarjan  qwq
    Nein[now]=Yeasion[now]=++ken;
    stack[++top]=now;
    flag[now]=true;
    ;i<line[now].size();i++)
    {
        int next=line[now][i];
        if(!Yeasion[next])
        {
            Tarjan(next);
            if(Nein[next]<Nein[now])
                Nein[now]=Nein[next];
        }
        else
            if(flag[next])
            Nein[now]=min(Yeasion[next],Nein[now]);
    }
    if(Nein[now]==Yeasion[now])
    {
        cnt++;//这里我们在Tarjan之后新建了一个图，然后我们资金编造了一个顺序。
        int pass;//顾名思义，过去的节点嘛...
        do
        {
            pass=stack[top--];//更新pass，进行退栈操作。
            belong[pass]=cnt;//表明原图中的pass点属于新图中的cnt节点。
            behind_value[cnt]+=value[pass];//更新新图中的cnt的节点大小
            flag[pass]=false;//退栈.....
        }while(pass!=now);
    }
    return ;
}
void link()//建新图
{
     ;i<=n;i++)
        ;j<line[i].size();j++)
        {
            int next=line[i][j];
            if(belong[i]!=belong[next])
            {
                tline[belong[i]].push_back(belong[next]);
                ind[belong[next]]+=;
            }
        }
}
void SPFA()
{
    while(!q.empty())
    {
        int pas=q.front();
        q.pop();
        inque[pas]=false;
        ;i<tline[pas].size();i++)
        {
            int next=tline[pas][i];
            if(dist[next]>dist[pas]-behind_value[next])
            {
                dist[next]=dist[pas]-behind_value[next];
                if(!inque[next])
                {
                    inque[next]=true;
                    q.push(next);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int a,b;
    ;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        line[a].push_back(b);
    }
    ;i<=n;i++)
        scanf("%d",&value[i]);
    ;i<=n;i++)
        if(!belong[i])
            Tarjan(i);
    scanf("%d%d",&s,&p);
    memset(dist,,sizeof(dist));
    dist[belong[s]]=-behind_value[belong[s]];
    q.push(belong[s]);
    inque[belong[s]]=true;
    ;
    ;i<=p;i++)
    {
        scanf("%d",&a);
        ans=min(ans,dist[belong[a]]);
    }
    printf("%d",-ans);
}

相关文章