【Tarjan】+【SPFA】APIO2009 Atm
2018-06-17 23:46:38来源:未知 阅读 ()
一、算法介绍
tarjan——求解有向图强连通分量。这个算法在本人的一篇blog中有介绍,这里就不赘述了。贴上介绍tarjan的的blog链接:http://www.cnblogs.com/Maki-Nishikino/p/5866191.html
那么接下来说说SPFA:
SPFA全称Shortest Path Faster Algorithm,用于求解单源最短路。既然名字中有“Faster”,那它就一定有过人之处,事实上它也的确比Dijkstra和Bellman-Ford更高效。
它的思路大致如下:
1、先用邻接表把图存下来,并且规定一个数组d,d[i]表示起点到i的最短路程;
2、建立一个队列,将起点放入队列;
3、对队首元素执行松弛操作,遍历所有以队首元素为起点的边,如果被遍历的边可以使到被遍历的边的终点的路径变短,那么就更新这个最短路径,并把被遍历的边的终点放到队尾;
4、每完成一次松弛,就令队首元素出队,重复3,直到队列里没有元素。
原谅博主懒得贴伪代码,我就直接讲题了,反正题解里也有模板#手动滑稽
二、APIO2009 Atm题解
原题链接(来自bzoj):http://www.lydsy.com/JudgeOnline/problem.php?id=1179
题目描述:
输入:
第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口
编号。接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来
的一行中有P个整数,表示P个有酒吧的路口的编号。
输出:
输出一个整数,表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
样例输入:
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
样例输出:
47
数据范围:
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
对于这道题,我们考虑先用tarjan求出它的所有强连通分量,再把同一个强连通分量上的ATM机的钱加起来,让一个强连通分量上的点缩成一个点。然后以市中心s为起点,用SPFA跑出s到其他点的最长(最有价值)路,比较酒吧所在点的d值,输出大的即可。
附上代码:
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 struct node 6 { 7 int v; 8 int next; 9 }; 10 int n,m; 11 node e[500010],map[500010];//邻接表存图 12 int st[500010],head[500010],cnt; 13 int atm[500010],money[500010]; 14 int d[500010],q[500010];//最短路径&SPFA要用的队列 15 void build(int a,int b) 16 { 17 e[++cnt].v=b; 18 e[cnt].next=st[a]; 19 st[a]=cnt; 20 }//建图找强连通分量 21 int stack[500010],top;//tarjan需要的栈 22 int dfn[500010],low[500010],dex;//时间戳(深搜序)、可回溯到的最早栈中时间戳、次序编号 23 bool vis[500010];//tarjan时判断点是否在栈中,SPFA时判断点是否在队列中 24 int color[500010],num;//表示同一强连通分量上的点 25 void tarjan(int x)//tarjan找强连通分量 26 { 27 dfn[x]=++dex; 28 low[x]=dex; 29 vis[x]=true; 30 stack[++top]=x;//当前点入栈 31 int i; 32 for(i=st[x];i!=0;i=e[i].next)//枚举以当前点为起点的边 33 { 34 int temp=e[i].v;//temp为当前被枚举边的终点 35 if(!dfn[temp])//如果当前边终点未被处理 36 { 37 tarjan(temp); 38 low[x]=min(low[x],low[temp]); 39 } 40 else if(vis[temp])low[x]=min(low[x],dfn[temp]); 41 } 42 if(dfn[x]==low[x]) 43 { 44 vis[x]=false; 45 color[x]=++num;//标记当前强连通分量内的点 46 while(stack[top]!=x)//栈顶元素依次出栈 47 { 48 color[stack[top]]=num; 49 vis[stack[top--]]=false; 50 } 51 top--; 52 } 53 } 54 void add()// 把同一强连通分量上的点缩成一个点,把这些点连成一张新图 55 { 56 cnt=0; 57 int i,j; 58 for(i=1;i<=n;i++) 59 { 60 for(j=st[i];j!=0;j=e[j].next) 61 { 62 int temp=e[j].v; 63 if(color[i]!=color[temp]) 64 { 65 map[++cnt].v=color[temp]; 66 map[cnt].next=head[color[i]]; 67 head[color[i]]=cnt; 68 } 69 } 70 71 } 72 } 73 void spfa(int x)//SPFA找最长路 74 { 75 memset(vis,false,sizeof(vis)); 76 int l=1,r=1; 77 q[l]=x;//初始点放入队列 78 vis[x]=true; 79 d[x]=money[x]; 80 while(l<=r) 81 { 82 int u=q[l++]; 83 for(int i=head[u];i!=0;i=map[i].next)//遍历所有以当前点为起点的边 84 { 85 int v=map[i].v; 86 if(d[v]<d[u]+money[v]) 87 { 88 d[v]=d[u]+money[v]; 89 if(vis[v])continue; 90 q[++r]=v;//如果当前拓展的边的终点不在队列里,就把它放入队尾 91 vis[v]=true; 92 } 93 } 94 vis[u]=false; 95 } 96 } 97 int main() 98 { 99 int a,b,i,s,p,o,ans=0; 100 scanf("%d%d",&n,&m); 101 for(i=1;i<=m;i++) 102 { 103 scanf("%d%d",&a,&b); 104 build(a,b); 105 }//建初始图 106 for(i=1;i<=n;i++) 107 { 108 if(!dfn[i])tarjan(i);//找强连通分量 109 } 110 add();//建新图 111 for(i=1;i<=n;i++) 112 { 113 scanf("%d",&atm[i]); 114 money[color[i]]+=atm[i]; 115 } 116 scanf("%d%d",&s,&p); 117 spfa(color[s]);//找单源最短路 118 for(i=1;i<=p;i++) 119 { 120 scanf("%d",&o); 121 ans=max(ans,d[color[o]]);//找到以酒吧为终点的最长路 122 } 123 printf("%d",ans); 124 return 0; 125 }
弱弱地说一句,本蒟蒻码字也不容易,转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/5868953.html
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Spfa 2019-09-17
- LG P2285 [模板]负环(spfa判负环) 2019-08-16
- Tarjan算法初探 (1):Tarjan如何求有向图的强连通分量 2019-04-11
- BZOJ1093: [ZJOI2007]最大半连通子图(tarjan dp) 2018-09-01
- 【C++学习笔记】强大的算法——spfa 2018-09-01
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