首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:09:26来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 4164  Solved: 1838
[Submit][Status][Discuss]

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;
}
dijstra

 

// 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;
}

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：C++ 日期 &amp; 时间

下一篇：POJ 3694 Network(Tarjan求割边+LCA)

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签