BZOJ 1179 Atm 题解
SPFA Algorithm
Tarjan Algorithm
Description
Input
第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数,表示P个有酒吧的路口的编号
Output
输出一个整数,表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
Sample Input
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
HINT
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
————————————————————————————分割线————————————————————————————
思路:
先用Tarjan算法求出途中的所有强连通分量,再讲每个分量值加和为点,再用SPFA算法求出以S为源点,最大价值的路径。
代码如下,(不是我的代码)
//Code By にしきのまき #include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
int v;
int next;
};
int n,m;
node e[],map[];//邻接表存图
int st[],head[],cnt;
int atm[],money[];
int d[],q[];//最短路径&SPFA要用的队列
void build(int a,int b)
{
e[++cnt].v=b;
e[cnt].next=st[a];
st[a]=cnt;
}//建图找强连通分量
int stack[],top;//tarjan需要的栈
int dfn[],low[],dex;//时间戳(深搜序)、可回溯到的最早栈中时间戳、次序编号
bool vis[];//tarjan时判断点是否在栈中,SPFA时判断点是否在队列中
int color[],num;//表示同一强连通分量上的点
void tarjan(int x)//tarjan找强连通分量
{
dfn[x]=++dex;
low[x]=dex;
vis[x]=true;
stack[++top]=x;//当前点入栈
int i;
for(i=st[x];i!=;i=e[i].next)//枚举以当前点为起点的边
{
int temp=e[i].v;//temp为当前被枚举边的终点
if(!dfn[temp])//如果当前边终点未被处理
{
tarjan(temp);
low[x]=min(low[x],low[temp]);
}
else if(vis[temp])low[x]=min(low[x],dfn[temp]);
}
if(dfn[x]==low[x])
{
vis[x]=false;
color[x]=++num;//标记当前强连通分量内的点
while(stack[top]!=x)//栈顶元素依次出栈
{
color[stack[top]]=num;
vis[stack[top--]]=false;
}
top--;
}
}
void add()// 把同一强连通分量上的点缩成一个点,把这些点连成一张新图
{
cnt=;
int i,j;
for(i=;i<=n;i++)
{
for(j=st[i];j!=;j=e[j].next)
{
int temp=e[j].v;
if(color[i]!=color[temp])
{
map[++cnt].v=color[temp];
map[cnt].next=head[color[i]];
head[color[i]]=cnt;
}
} }
}
void spfa(int x)//SPFA找最长路
{
memset(vis,false,sizeof(vis));
int l=,r=;
q[l]=x;//初始点放入队列
vis[x]=true;
d[x]=money[x];
while(l<=r)
{
int u=q[l++];
for(int i=head[u];i!=;i=map[i].next)//遍历所有以当前点为起点的边
{
int v=map[i].v;
if(d[v]<d[u]+money[v])
{
d[v]=d[u]+money[v];
if(vis[v])continue;
q[++r]=v;//如果当前拓展的边的终点不在队列里,就把它放入队尾
vis[v]=true;
}
}
vis[u]=false;
}
}
int main()
{
int a,b,i,s,p,o,ans=;
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
build(a,b);
}//建初始图
for(i=;i<=n;i++)
{
if(!dfn[i])tarjan(i);//找强连通分量
}
add();//建新图
for(i=;i<=n;i++)
{
scanf("%d",&atm[i]);
money[color[i]]+=atm[i];
}
scanf("%d%d",&s,&p);
spfa(color[s]);//找单源最短路
for(i=;i<=p;i++)
{
scanf("%d",&o);
ans=max(ans,d[color[o]]);//找到以酒吧为终点的最长路
}
printf("%d",ans);
return ;
}
2016-09-14 20:00:54
(完)
BZOJ 1179 Atm 题解的更多相关文章
-
bzoj 1179 Atm
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1179 题解: 一道比较综合的图论题 直接讲正解: 如果这个图G中存在某个强连通分量,那么这 ...
-
BZOJ 1179 Atm(强连通分量缩点+DP)
题目说可以通过一条边多次,且点权是非负的,所以如果走到图中的一个强连通分量,那么一定可以拿完这个强连通分量上的money. 所以缩点已经很明显了.缩完点之后图就是一个DAG,对于DAG可以用DP来求出 ...
-
bzoj 1179 [APIO 2009]Atm(APIO水题) - Tarjan - spfa
Input 第一行包含两个整数N.M.N表示路口的个数,M表示道路条数.接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号.接下来N行,每行一 ...
-
BZOJ 1179 [Apio2009]Atm(强连通分量)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1179 [题目大意] 给出一张有向带环点权图,给出一些终点,在路径中同一个点的点权只能累 ...
-
BZOJ 1179: [Apio2009]Atm( tarjan + 最短路 )
对于一个强连通分量, 一定是整个走或者不走, 所以tarjan缩点然后跑dijkstra. ------------------------------------------------------ ...
-
bzoj 1179 [Apio2009]Atm 缩点+最短路
[Apio2009]Atm Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 4290 Solved: 1893[Submit][Status][Dis ...
-
BZOJ 1179 抢掠计划atm (缩点+有向无环图DP)
手动博客搬家: 本文发表于20170716 10:58:18, 原地址https://blog.csdn.net/suncongbo/article/details/81061601 https:// ...
-
bzoj 1179[Apio2009]Atm (tarjan+spfa)
题目 输入 第一行包含两个整数N.M.N表示路口的个数,M表示道路条数.接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号.接下来N行,每行一 ...
-
bzoj 1179: [Apio2009]Atm
Description Input 第 一行包含两个整数N.M.N表示路口的个数,M表示道路条数.接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路 的起点和终点的 ...
随机推荐
-
SVN服务器和客户端安装教程
SVN是什么?有何用? SVN是Subversion的简称,是一个开放源代码的版本控制系统,相较于RCS.CVS,它采用了分支管理系统,它的设计目标就是取代CVS.互联网上很多版本控制服务已从CVS迁 ...
-
jvisualvm参数配置
1.java 命令启动 nohup java -Dlocalcfg=true -Dcom.sun.management.jmxremote.port=9998 -Dcom.sun.management ...
-
XE6移动开发环境搭建之IOS篇(2):安装VM9虚拟机(有图有真相)
网上能找到的关于Delphi XE系列的移动开发环境的相关文章甚少,本文尽量以详细的图文内容.傻瓜式的表达来告诉你想要的答案. 原创作品,请尊重作者劳动成果,转载请注明出处!!! 1.安装VM9英文原 ...
-
nginx处理静态资源的配置
修改nginx.conf文件,用于nginx处理静态资源. 主要配置如下(在server配置中加入location配置即可): server { listen 80; server_name 123. ...
-
CodeForces 213B Numbers
$dp$,组合数. $dp[i][j]$表示只用数字$i$,$i+1$,$i+2$......,$9$,凑成长度为$j$的并且数字$i$到$9$符合要求的方案数.只要枚举数字$i$用几个就可以转移了. ...
-
java 文件字节输入流
Example10_4.java import java.io.*; public class Example10_4 { public static void main(String args[]) ...
-
CSS常用字体Unicode 编码
在 CSS 中设置字体名称,直接写中文是可以的.但是在文件编码(GB2312.UTF-8 等)不匹配时会产生乱码的错误. 为此,在 CSS 直接使用 Unicode 编码来写字体名称可以避免这些错误. ...
-
jq实现数字增加或者减少的动画
效果图: 1.HTML: <div class="up"></div> <br> <div class="down"& ...
-
trace跟踪代码运行
System.Diagnostics命名空间中. 1.Trace.Assert(a==12,"等于就不输出,不等于弹出对话框"); 名称 描述 Assert(Boolean ...
-
Thunder团队第七周 - Scrum会议1
Scrum会议1 小组名称:Thunder 项目名称:i阅app Scrum Master:杨梓瑞 工作照片: 参会成员: 王航:http://www.cnblogs.com/wangh013/ 李传 ...