BZOJ 1179: [Apio2009]Atm(tarjan+SPFA)

Description

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定, 在每个路口都设立了一个 Siruser

i 银行的 ATM 取款机。令人奇怪的是,Siruseri 的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。Bandit

ji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发,沿着单向道路行驶,抢劫所有他

途径的 ATM 机,最终他将在一个酒吧庆 祝他的胜利。使用高超的黑客技术,他获知了每个 ATM 机中可以掠取的

现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口

或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机 里面就不会再有钱了。 例如,假设该城中有 6 个

路口,道路的连接情况如下图所示:

市中心在路口 1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了

路口的上方。在这个例子中,Banditji 能抢 劫的现金总数为 47,实施的抢劫路线是:1-2-4-1-2-3-5。

Input

第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。

接下来M行,每行两个整数,这两个整数都在1到N之间,

第i+1行的两个整数表示第i条道路的起点和终点的路口编号。

接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。

接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。

接下来的一行中有P个整数,表示P个有酒吧的路口的编号

N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。

输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

Output

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

Sample Input

6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6

Sample Output

47

HINT

Source

思路比较简单,缩起点来求最长路即可

但是为什么dijstra不能求最长路??黑人问号.jpg

// luogu-judger-enable-o2
#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
#include<queue>
#define Pair pair<int,int>
#define F first
#define S second
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int u,v,w,nxt;
}E[MAXN],edge[MAXN];
int headE[MAXN],numE=1,head[MAXN],num=1;
inline void add_edge(int x,int y)
{
    E[numE].u=x;
    E[numE].v=y;
    E[numE].nxt=headE[x];
    headE[x]=numE++;
}
inline void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int N,M,S,P;
int money[MAXN],pos[MAXN],sum[MAXN];
int vis[MAXN],dfn[MAXN],low[MAXN],color[MAXN],colornum=0,tot=0;
stack<int>s;
void tarjan(int now)
{
    dfn[now]=low[now]=++tot;
    s.push(now);
    vis[now]=1;
    for(int i=headE[now];i!=-1;i=E[i].nxt)
    {
        if(!dfn[E[i].v]) 
            tarjan(E[i].v),low[now]=min(low[now],low[E[i].v]);
        else if(vis[E[i].v]) 
            low[now]=min(low[now],dfn[E[i].v]);
    }
    if(low[now]==dfn[now])
    {
        int h;
        colornum++;
        do
        {
            h=s.top();
            color[h]=colornum;
            sum[colornum]+=money[h];
            vis[h]=0;
            s.pop();
            
        }while(h!=now);
    }
}
int dis[MAXN];
void Dijstra()
{
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<Pair>q;
    dis[color[S]]=sum[color[S]];
    q.push(make_pair(dis[color[S]],color[S]));
    while(q.size()!=0)
    {
        while(vis[q.top().S]&&q.size()>0) q.pop();
        int p=q.top().S;
        vis[p]=1;
        for(int i=head[p];i!=-1;i=edge[i].nxt)
            if(vis[edge[i].v]==0&&dis[edge[i].v]<dis[p]+sum[edge[i].v])
                dis[edge[i].v]=dis[p]+sum[edge[i].v],
                q.push(make_pair(dis[edge[i].v],edge[i].v));
    }
    int ans=0;
    for(int i=1;i<=P;i++)
        ans=max(ans,dis[color[pos[i]]]);
    printf("%d",ans);
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    memset(headE,-1,sizeof(headE));
    N=read();M=read();
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);
    }
    for(int i=1;i<=N;i++) money[i]=read();
    S=read();P=read();
    for(int i=1;i<=P;i++) pos[i]=read(); 
    for(int i=1;i<=N;i++)
        if(!dfn[i]) 
            tarjan(i);
    for(int i=1;i<=numE-1;i++)
        if(color[E[i].u]!=color[E[i].v])    
            AddEdge(color[E[i].u],color[E[i].v]);
    Dijstra();
    return 0;
}
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
#include<queue>
#define Pair pair<int,int>
#define F first
#define S second
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int u,v,w,nxt;
}E[MAXN],edge[MAXN];
int headE[MAXN],numE=1,head[MAXN],num=1;
inline void add_edge(int x,int y)
{
    E[numE].u=x;
    E[numE].v=y;
    E[numE].nxt=headE[x];
    headE[x]=numE++;
}
inline void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int N,M,S,P;
int money[MAXN],pos[MAXN],sum[MAXN];
int vis[MAXN],dfn[MAXN],low[MAXN],color[MAXN],colornum=0,tot=0;
stack<int>s;
void tarjan(int now)
{
    dfn[now]=low[now]=++tot;
    s.push(now);
    vis[now]=1;
    for(int i=headE[now];i!=-1;i=E[i].nxt)
    {
        if(!dfn[E[i].v]) 
            tarjan(E[i].v),low[now]=min(low[now],low[E[i].v]);
        else if(vis[E[i].v]) 
            low[now]=min(low[now],dfn[E[i].v]);
    }
    if(low[now]==dfn[now])
    {
        int h;
        colornum++;
        do
        {
            h=s.top();
            color[h]=colornum;
            sum[colornum]+=money[h];
            vis[h]=0;
            s.pop();
            
        }while(h!=now);
    }
}
int dis[MAXN];
void Dijstra()
{
    memset(dis,0,sizeof(dis));dis[color[S]]=sum[color[S]];
    memset(vis,0,sizeof(vis));vis[color[S]]=1;
    queue<int>q;
    q.push(color[S]);
    while(q.size()!=0)
    {
        int p=q.front();q.pop();
        vis[p]=0;
        for(int i=head[p];i!=-1;i=edge[i].nxt)
        {
            if(dis[edge[i].v]<dis[p]+edge[i].w)
            {
                dis[edge[i].v]=dis[p]+edge[i].w;
                if(vis[edge[i].v]==0)
                    vis[edge[i].v]=1,q.push(edge[i].v);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=P;i++)
        ans=max(ans,dis[color[pos[i]]]);
    printf("%d",ans);
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
 //   freopen("a.out","w",stdout);
    #else
    #endif
    memset(head,-1,sizeof(head));
    memset(headE,-1,sizeof(headE));
    N=read();M=read();
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read();
        add_edge(x,y);
    }
    for(int i=1;i<=N;i++) money[i]=read();
    S=read();P=read();
    for(int i=1;i<=P;i++) pos[i]=read(); 
    for(int i=1;i<=N;i++)
        if(!dfn[i]) 
            tarjan(i);
    for(int i=1;i<=numE-1;i++)
        if(color[E[i].u]!=color[E[i].v])    
            AddEdge(color[E[i].u],color[E[i].v],sum[color[E[i].v]]);
    Dijstra();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

4大分析工具的代码表白术,520花式秀恩爱!

尽管笛卡尔和瑞典公主的故事已被证实只是杜撰,但因这个故事出名的心形函数被广为流传。今天又是一个虐单身狗的日分析师子,面对各种毫无新意的表白方式,让我们来看看理工...

32410
来自专栏大数据钻研

由浅入深的前端面试题 和矫情的“浪漫主义”诗句

好吧,我承认太标题党了,这篇文章是通过一道前端面试题引出的纯技术讨论。我先要矫情无比的从中外诗歌说起。 传统的佛学经典里,被世人熟知的有这样一句话:“一花一世界...

34510
来自专栏菩提树下的杨过

温故而知新:设计模式之装饰模式(Decorator)

小时候对日本的动画片十分着迷,“圣斗士”是我的最爱;长大后也曾经一度对“海贼王”十分痴迷;大学看武侠小说时,也特别喜欢那种主人公有奇遇的情况:吃到一颗千年异果,...

2026
来自专栏IT派

你知道 Python 这五个有趣的彩蛋吗?

当一门编程语言是开源的时候,往往会有产生一些搞笑和有趣的东西。通常,这意味着社区的贡献者会为该语言添加一些有趣和特别的彩蛋以及隐藏的特性(当然前提是不会增加在生...

1152
来自专栏数据结构与算法

2017.10.26水题大作战部分题解

感觉这一场的题目超纲了QWQ。。。 好难啊QWQ。。。。。。 A  P2907 [USACO08OPEN]农场周围的道路Roads Around The Far...

3114
来自专栏斑斓

Martin Odersky访谈录所思

ThoughtWorks的「TW洞见」在4月发布了对Scala之父Martin Odersky的访谈。Odersky的回答显得言简意赅,仔细分析,仍然能从中收获...

3315
来自专栏带你撸出一手好代码

暗号与二进制

「暗号」这个词的意义想必大家都熟悉, 它也是人与人的一种交流方式,只是它的规则并不如我们使用的语言或文字一样由大众所掌握, 因此当人们想传递一些私密的信息又不想...

41214
来自专栏tkokof 的技术,小趣及杂念

编个“猜数字”玩玩

一日午晌,顿觉百无聊赖,阵阵哈切之余,竟忆起儿时游玩之小游戏,名曰“猜数字”,此物规则甚是简单,游玩之时仅需猜测一四位数字,接着便可得到相应之正误结果,然后依此...

461
来自专栏恰同学骚年

自己动手写游戏:坦克撕逼大战

START:最近在公交车上无聊,于是用平板看了看下载的坦克大战的开发教程,于是在晚上回家后花了两天模仿了一个,现在来总结一下。

1856
来自专栏杨建荣的学习笔记

重温二分查找算法(r4笔记第66天)

二分查找在学习算法的时候会涉及到,算是一个基本的分治思想,对于算法的实现大家也都是很熟悉的,但是这个时候真会犯眼高手低的毛病。不信你自己试试,看你能够在段时间内...

4045

扫码关注云+社区

领取腾讯云代金券